[PATCH v5 0/4] rust: adds Bitmap API, ID pool and bindings

[PATCH v5 0/4] rust: adds Bitmap API, ID pool and bindings

[Burak Emir]

This series adds a Rust bitmap API for porting the approach from 
commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.

The Rust bitmap API provides a safe abstraction to underlying bitmap
and bitops operations. For now, only includes method necessary for 
dbitmap.h, more can be added later. We perform bounds checks for 
hardening, violations are programmer errors that result in panics.

This version includes an optimization to represent the bitmap inline,
as suggested by Yury.

The Rust equivalent of dbitmap.h is included as id_pool.rs, which is
tightly coupled to the bitmap API. Includes an example of usage
that requires releasing a spinlock, as expected in Binder driver.

This is v5 of a patch introducing Rust bitmap API [v4]. Thanks
for all the helpful comments, this series has improved significantly
as a result of your work.

Changes v4 --> v5: (suggested by Yury and Alice)
- rebased on next-20250318
- split MAINTAINERS changes
- no dependencies on [1] and [2] anymore - Viresh,
  please do add a separate section if you want to maintain cpumask.rs
  separately.
- imports atomic and non-atomic variants, introduces a naming convention
  set_bit and set_bit_atomic on the Rust side.
- changed naming and comments. Keeping `new`.
- change dynamic_id_pool to id_pool
- represent bitmap inline when possible
- add some more tests
- add bqe@google.com as M: for the Rust abstractions

Changes v3 --> v4:
- Rebased on Viresh's v3 [2].
- split into multiple patches, separate Rust and bindings. (Yury)
- adds dynamic_id_pool.rs to show the Binder use case. (Yury)
- include example usage that requires release of spinlock (Alice)
- changed bounds checks to `assert!`, shorter (Yury)
- fix param names in binding helpers. (Miguel)
- proper rustdoc formatting, and use examples as kunit tests. (Miguel)
- reduce number of Bitmap methods, and simplify API through
  use Option<usize> to handle the "not found" case.
- make Bitmap pointer accessors private, so Rust Bitmap API
  provides an actual abstraction boundary (Tamir)
- we still return `AllocError` in `Bitmap::new` in case client code
  asks for a size that is too large. Intentionally
  different from other bounds checks because it is not about
  access but allocation, and we expect that client code need
  never handle AllocError and nbits > u32::MAX situations
  differently.

Changes v2 --> v3:
- change `bitmap_copy` to `copy_from_bitmap_and_extend` which
  zeroes out extra bits. This enables dbitmap shrink and grow use
  cases while offering a consistent and understandable Rust API for
  other uses (Alice)

Changes v1 --> v2:
- Rebased on Yury's v2 [1] and Viresh's v3 [2] changes related to
  bitmap.
- Removed import of `bindings::*`, keeping only prefix (Miguel)
- Renamed panic methods to make more explicit (Miguel)
- use markdown in doc comments and added example/kunit test (Miguel)
- Added maintainer section for BITOPS API BINDINGS [RUST] (Yury)
- Added M: entry for bitmap.rs which goes to Alice (Viresh, Alice)
- Changed calls from find_* to _find_*, removed helpers (Yury)
- Use non-atomic __set_bit and __clear_bit from Bitmap Rust API (Yury)

Link [1] https://lore.kernel.org/all/20250224233938.3158-1-yury.norov@gmail.com/
Link [2] https://lore.kernel.org/rust-for-linux/cover.1742296835.git.viresh.kumar@linaro.org/
Link [v4]: https://lore.kernel.org/lkml/20250318164221.1533590-1-bqe@google.com/

Burak Emir (4):
  rust: add bindings for bitmap.h
  rust: add bindings for bitops.h
  rust: add bitmap API.
  rust: add dynamic ID pool abstraction for bitmap

 MAINTAINERS                     |  14 ++
 rust/bindings/bindings_helper.h |   1 +
 rust/helpers/bitmap.c           |   9 +
 rust/helpers/bitops.c           |  23 +++
 rust/helpers/helpers.c          |   2 +
 rust/kernel/bitmap.rs           | 293 ++++++++++++++++++++++++++++++++
 rust/kernel/id_pool.rs          | 201 ++++++++++++++++++++++
 rust/kernel/lib.rs              |   2 +
 8 files changed, 545 insertions(+)
 create mode 100644 rust/helpers/bitmap.c
 create mode 100644 rust/helpers/bitops.c
 create mode 100644 rust/kernel/bitmap.rs
 create mode 100644 rust/kernel/id_pool.rs

-- 
2.49.0.395.g12beb8f557-goog

[PATCH v5 1/4] rust: add bindings for bitmap.h

[Burak Emir]

Makes the bitmap_copy_and_extend inline function available to Rust.
Adds F: to existing MAINTAINERS section BITMAP API BINDINGS [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS                     | 1 +
 rust/bindings/bindings_helper.h | 1 +
 rust/helpers/bitmap.c           | 9 +++++++++
 rust/helpers/helpers.c          | 1 +
 4 files changed, 12 insertions(+)
 create mode 100644 rust/helpers/bitmap.c

diff --git a/MAINTAINERS b/MAINTAINERS
index ebf7fa9a814d..52fc47a28b4c 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4111,6 +4111,7 @@ F:	tools/lib/find_bit.c
 BITMAP API BINDINGS [RUST]
 M:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
+F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
 BITOPS API
diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
index fcefe3068a28..4f9374c2d7e5 100644
--- a/rust/bindings/bindings_helper.h
+++ b/rust/bindings/bindings_helper.h
@@ -7,6 +7,7 @@
  */
 
 #include <kunit/test.h>
+#include <linux/bitmap.h>
 #include <linux/blk-mq.h>
 #include <linux/blk_types.h>
 #include <linux/blkdev.h>
diff --git a/rust/helpers/bitmap.c b/rust/helpers/bitmap.c
new file mode 100644
index 000000000000..a50e2f082e47
--- /dev/null
+++ b/rust/helpers/bitmap.c
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bitmap.h>
+
+void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long *from,
+		unsigned int count, unsigned int size)
+{
+	bitmap_copy_and_extend(to, from, count, size);
+}
diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
index e1c21eba9b15..d4a60f1d6cc4 100644
--- a/rust/helpers/helpers.c
+++ b/rust/helpers/helpers.c
@@ -7,6 +7,7 @@
  * Sorted alphabetically.
  */
 
+#include "bitmap.c"
 #include "blk.c"
 #include "bug.c"
 #include "build_assert.c"
-- 
2.49.0.395.g12beb8f557-goog

[PATCH v5 2/4] rust: add bindings for bitops.h

[Burak Emir]

Makes atomic set_bit and clear_bit inline functions as well as the
non-atomic variants __set_bit and __clear_bit available to Rust.
Adds a new MAINTAINERS section BITOPS API BINDINGS [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS            |  5 +++++
 rust/helpers/bitops.c  | 23 +++++++++++++++++++++++
 rust/helpers/helpers.c |  1 +
 3 files changed, 29 insertions(+)
 create mode 100644 rust/helpers/bitops.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 52fc47a28b4c..7cd15c25a43c 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4128,6 +4128,11 @@ F:	include/linux/bitops.h
 F:	lib/test_bitops.c
 F:	tools/*/bitops*
 
+BITOPS API BINDINGS [RUST]
+M:	Yury Norov <yury.norov@gmail.com>
+S:	Maintained
+F:	rust/helpers/bitops.c
+
 BLINKM RGB LED DRIVER
 M:	Jan-Simon Moeller <jansimon.moeller@gmx.de>
 S:	Maintained
diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c
new file mode 100644
index 000000000000..2eaab292db4f
--- /dev/null
+++ b/rust/helpers/bitops.c
@@ -0,0 +1,23 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bitops.h>
+
+void rust_helper___set_bit(unsigned int nr, unsigned long *addr)
+{
+	__set_bit(nr, addr);
+}
+
+void rust_helper___clear_bit(unsigned int nr, unsigned long *addr)
+{
+	__clear_bit(nr, addr);
+}
+
+void rust_helper_set_bit(unsigned int nr, unsigned long *addr)
+{
+	set_bit(nr, addr);
+}
+
+void rust_helper_clear_bit(unsigned int nr, unsigned long *addr)
+{
+	clear_bit(nr, addr);
+}
diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
index d4a60f1d6cc4..0c25cc86a52a 100644
--- a/rust/helpers/helpers.c
+++ b/rust/helpers/helpers.c
@@ -8,6 +8,7 @@
  */
 
 #include "bitmap.c"
+#include "bitops.c"
 #include "blk.c"
 #include "bug.c"
 #include "build_assert.c"
-- 
2.49.0.395.g12beb8f557-goog

[PATCH v5 3/4] rust: add bitmap API.

[Burak Emir]

Provides an abstraction for C bitmap API and bitops operations.
Includes enough to implement a Binder data structure that was
introduced in commit 15d9da3f818c ("binder: use bitmap for faster
descriptor lookup"), namely drivers/android/dbitmap.h.

The implementation is optimized to represent the bitmap inline
if it would take the space of a pointer. This saves allocations.
We offer a safe API through bounds checks which panic if violated.

We use the `usize` type for sizes and indices into the bitmap,
because Rust generally always uses that type for indices and lengths
and it will be more convenient if the API accepts that type. This means
that we need to perform some casts to/from u32 and usize, since the C
headers use unsigned int instead of size_t/unsigned long for these
numbers in some places.

Adds new MAINTAINERS section BITMAP API [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS           |   7 +
 rust/kernel/bitmap.rs | 293 ++++++++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs    |   1 +
 3 files changed, 301 insertions(+)
 create mode 100644 rust/kernel/bitmap.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index 7cd15c25a43c..bc8f05431689 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4114,6 +4114,13 @@ S:	Maintained
 F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
+BITMAP API [RUST]
+M:	Alice Ryhl <aliceryhl@google.com>
+M:	Burak Emir <bqe@google.com>
+R:	Yury Norov <yury.norov@gmail.com>
+S:	Maintained
+F:	rust/kernel/bitmap.rs
+
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
 R:	Rasmus Villemoes <linux@rasmusvillemoes.dk>
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
new file mode 100644
index 000000000000..118dceaf2b4b
--- /dev/null
+++ b/rust/kernel/bitmap.rs
@@ -0,0 +1,293 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+//! Rust API for bitmap.
+//!
+//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
+
+use crate::alloc::{AllocError, Flags};
+use crate::bindings;
+use core::ptr::NonNull;
+
+/// Holds either a pointer to array of `unsigned long` or a small bitmap.
+#[repr(C)]
+union BitmapRepr {
+  bitmap: usize,
+  ptr: NonNull<usize>
+}
+
+/// Represents a bitmap.
+///
+/// Wraps underlying C bitmap API.
+///
+/// # Examples
+///
+/// Basic usage
+///
+/// ```
+/// use kernel::alloc::flags::GFP_KERNEL;
+/// use kernel::bitmap::Bitmap;
+///
+/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
+/// assert_eq!(16, b.len());
+/// for i in 0..16 {
+///   if i % 4 == 0 {
+///     b.set_bit(i);
+///   }
+/// }
+/// assert_eq!(Some(1), b.next_zero_bit(0));
+/// assert_eq!(Some(5), b.next_zero_bit(5));
+/// assert_eq!(Some(12), b.last_bit());
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Requesting too large values results in [`AllocError`]
+///
+/// ```
+/// use kernel::alloc::flags::GFP_KERNEL;
+/// use kernel::bitmap::Bitmap;
+/// assert!(Bitmap::new(1 << 31, GFP_KERNEL).is_err());
+/// ```
+///
+/// # Invariants
+///
+/// * `nbits` is `<= i32::MAX - 1` and never changes.
+/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a bitmap.
+/// * otherwise, `repr` holds a non-null pointer that was obtained from a
+///   successful call to `bitmap_zalloc` and holds the address of an initialized
+///   array of `unsigned long` that is large enough to hold `nbits` bits.
+pub struct Bitmap {
+    /// Representation of bitmap.
+    repr: BitmapRepr,
+    /// Length of this bitmap. Must be `<= i32::MAX - 1`.
+    nbits: usize,
+}
+
+impl Drop for Bitmap {
+    fn drop(&mut self) {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            return
+        }
+        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
+        //
+        // INVARIANT: there is no other use of the `self.ptr` after this
+        // call and the value is being dropped so the broken invariant is
+        // not observable on function exit.
+        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
+    }
+}
+
+impl Bitmap {
+    /// Constructs a new [`Bitmap`].
+    ///
+    /// If the length `nbits` is small enough to admit inline representation, this
+    /// implementation does not allocate.
+    ///
+    /// Fails with [`AllocError`] when the [`Bitmap`] could not be allocated. This
+    /// includes the case when `nbits` is greater than `i32::MAX - 1`.
+    #[inline]
+    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
+        if nbits <= bindings::BITS_PER_LONG as _ {
+            return Ok(Bitmap { repr: BitmapRepr { bitmap: 0 }, nbits });
+        }
+        if nbits <= i32::MAX.try_into().unwrap() {
+            let nbits_u32 = u32::try_from(nbits).unwrap();
+            // SAFETY: `nbits <= i32::MAX - 1` and the C function handles `nbits == 0`.
+            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
+            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
+            // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
+            return Ok(Bitmap {
+                repr: BitmapRepr { ptr },
+                nbits,
+            });
+        }
+        Err(AllocError)
+    }
+
+    /// Returns length of this [`Bitmap`].
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.nbits
+    }
+
+    /// Returns a mutable raw pointer to the backing [`Bitmap`].
+    #[inline]
+    fn as_mut_ptr(&mut self) -> *mut usize {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            // SAFETY: Bitmap is represented inline.
+            unsafe { core::ptr::addr_of_mut!(self.repr.bitmap) }
+        } else {
+            // SAFETY: Bitmap is represented as array of `unsigned long`.
+            unsafe { self.repr.ptr.as_mut() }
+        }
+    }
+
+    /// Returns a raw pointer to the backing [`Bitmap`].
+    #[inline]
+    fn as_ptr(&self) -> *const usize {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            // SAFETY: Bitmap is represented inline.
+            unsafe { core::ptr::addr_of!(self.repr.bitmap) }
+        } else {
+            // SAFETY: Bitmap is represented as array of `unsigned long`.
+            unsafe { self.repr.ptr.as_ptr() }
+        }
+    }
+
+    /// Set bit with index `index`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn set_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: Bit `index` is within bounds.
+        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Set bit with index `index`, atomically.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn set_bit_atomic(&self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds and `set_bit` is atomic.
+        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
+    }
+
+    /// Clear bit with index `index`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn clear_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds.
+        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Clear bit with index `index`, atomically.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn clear_bit_atomic(&self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds and `clear_bit` is atomic.
+        unsafe { bindings::clear_bit(index as u32, self.as_ptr() as *mut usize) };
+    }
+
+    /// Copy `src` into this [`Bitmap`] and set any remaining bits to zero.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
+    /// assert_eq!(None, long_bitmap.last_bit());
+    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
+    /// short_bitmap.set_bit(7);
+    ///
+    /// long_bitmap.copy_and_extend(&short_bitmap);
+    /// assert_eq!(Some(7), long_bitmap.last_bit());
+    ///
+    /// long_bitmap.clear_bit(7);
+    /// assert_eq!(None, long_bitmap.last_bit());
+    ///
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn copy_and_extend(&mut self, src: &Bitmap) {
+        let len = core::cmp::min(src.nbits, self.nbits);
+        // SAFETY: access to `self` and `src` is within bounds.
+        unsafe {
+            bindings::bitmap_copy_and_extend(
+                self.as_mut_ptr(),
+                src.as_ptr(),
+                len as u32,
+                self.nbits as u32,
+            )
+        };
+    }
+
+    /// Finds last bit that is set.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let bitmap = Bitmap::new(64, GFP_KERNEL)?;
+    /// match bitmap.last_bit() {
+    ///     Some(idx) => {
+    ///         pr_info!("The last bit has index {idx}.\n");
+    ///     }
+    ///     None => {
+    ///         pr_info!("All bits in this bitmap are 0.\n");
+    ///     }
+    /// }
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn last_bit(&self) -> Option<usize> {
+        // SAFETY: `nbits == 0` is supported and access is within bounds.
+        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+
+    /// Finds next zero bit, starting from `start`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
+        assert!(
+            start < self.nbits,
+            "Offset `start` must be < {}, was {}",
+            self.nbits,
+            start
+        );
+
+        // SAFETY: access is within bounds.
+        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, start) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index 6b46bc481d94..9f675c0841e6 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -36,6 +36,7 @@
 pub use ffi;
 
 pub mod alloc;
+pub mod bitmap;
 #[cfg(CONFIG_BLOCK)]
 pub mod block;
 #[doc(hidden)]
-- 
2.49.0.395.g12beb8f557-goog

[PATCH v5 4/4] rust: add dynamic ID pool abstraction for bitmap

[Burak Emir]

This is a port of the Binder data structure introduced in commit
15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
Rust.

Like drivers/android/dbitmap.h, the ID pool abstraction lets
clients acquire and release IDs. The implementation uses a bitmap to
know what IDs are in use, and gives clients fine-grained control over
the time of allocation. This fine-grained control is needed in the
Android Binder. We provide an example that release a spinlock for
allocation and unit tests (rustdoc examples).

The implementation is not aware that the underlying Bitmap abstraction
handles lengths below BITS_PER_LONG without allocation.

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS            |   1 +
 rust/kernel/id_pool.rs | 201 +++++++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs     |   1 +
 3 files changed, 203 insertions(+)
 create mode 100644 rust/kernel/id_pool.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index bc8f05431689..61ac5da0dfbf 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4120,6 +4120,7 @@ M:	Burak Emir <bqe@google.com>
 R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
 F:	rust/kernel/bitmap.rs
+F:	rust/kernel/id_pool.rs
 
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
new file mode 100644
index 000000000000..8f07526bb580
--- /dev/null
+++ b/rust/kernel/id_pool.rs
@@ -0,0 +1,201 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+//! Rust API for an ID pool backed by a `Bitmap`.
+
+use crate::alloc::{AllocError, Flags};
+use crate::bitmap::Bitmap;
+
+/// Represents a dynamic ID pool backed by a `Bitmap`.
+///
+/// Clients acquire and release IDs from zero bits in a bitmap.
+///
+/// The ID pool can grow or shrink as needed. It has been designed
+/// to support the scenario where users need to control the time
+/// of allocation of a new backing bitmap, which may require release
+/// of locks.
+/// These operations then, are verified to determine if the grow or
+/// shrink is sill valid.
+///
+/// # Examples
+///
+/// Basic usage
+///
+/// ```
+/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+/// use kernel::id_pool::IdPool;
+///
+/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
+/// for i in 0..64 {
+///   assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
+/// }
+///
+/// pool.release_id(23);
+/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
+///
+/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
+/// let resizer = pool.grow_alloc().alloc(GFP_KERNEL)?;
+/// pool.grow(resizer);
+///
+/// assert_eq!(pool.acquire_next_id(0), Some(64));
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Releasing spinlock to grow the pool
+///
+/// ```no_run
+/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+/// use kernel::sync::{new_spinlock, SpinLock};
+/// use kernel::id_pool::IdPool;
+///
+/// fn get_id_maybe_alloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
+///   let mut pool = guarded_pool.lock();
+///   loop {
+///     match pool.acquire_next_id(0) {
+///       Some(index) => return Ok(index),
+///       None => {
+///         let alloc_request = pool.grow_alloc();
+///         drop(pool);
+///         let resizer = alloc_request.alloc(GFP_KERNEL)?;
+///         pool = guarded_pool.lock();
+///         pool.grow(resizer)
+///       }
+///     }
+///   }
+/// }
+/// ```
+pub struct IdPool {
+    map: Bitmap,
+}
+
+/// Returned when the `IdPool` should change size.
+pub struct AllocRequest {
+    nbits: usize,
+}
+
+/// Contains an allocated `Bitmap` for resizing `IdPool`.
+pub struct PoolResizer {
+    new: Bitmap,
+}
+
+impl AllocRequest {
+    /// Allocates a new `Bitmap` for `IdPool`.
+    pub fn alloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
+        let new = Bitmap::new(self.nbits, flags)?;
+        Ok(PoolResizer { new })
+    }
+}
+
+impl IdPool {
+    /// Constructs a new `[IdPool]`.
+    #[inline]
+    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
+        let map = Bitmap::new(nbits, flags)?;
+        Ok(Self { map })
+    }
+
+    /// Returns how many IDs this pool can currently have.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
+
+    /// Returns an [`AllocRequest`] if the [`IdPool`] can be shrunk, [`None`] otherwise.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::id_pool::{AllocRequest, IdPool};
+    ///
+    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
+    /// let alloc_request = pool.shrink_alloc().ok_or(AllocError)?;
+    /// let resizer = alloc_request.alloc(GFP_KERNEL)?;
+    /// pool.shrink(resizer);
+    /// assert_eq!(pool.len(), kernel::bindings::BITS_PER_LONG as usize);
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
+        let len = self.map.len();
+        if len <= bindings::BITS_PER_LONG as usize {
+            return None;
+        }
+        /*
+         * Determine if the bitmap can shrink based on the position of
+         * its last set bit. If the bit is within the first quarter of
+         * the bitmap then shrinking is possible. In this case, the
+         * bitmap should shrink to half its current size.
+         */
+        match self.map.last_bit() {
+            Some(bit) => {
+                if bit < (len >> 2) {
+                    Some(AllocRequest { nbits: len >> 1 })
+                } else {
+                    None
+                }
+            }
+            None => Some(AllocRequest {
+                nbits: bindings::BITS_PER_LONG as usize,
+            }),
+        }
+    }
+
+    /// Shrinks pool by using a new `Bitmap`, if still possible.
+    #[inline]
+    pub fn shrink(&mut self, mut resizer: PoolResizer) {
+        // Verify that shrinking is still possible. The `resizer`
+        // bitmap might have been allocated without locks, so this call
+        // could now be outdated. In this case, drop `resizer` and move on.
+        if let Some(AllocRequest { nbits }) = self.shrink_alloc() {
+            if nbits <= resizer.new.len() {
+                resizer.new.copy_and_extend(&self.map);
+                self.map = resizer.new;
+                return;
+            }
+        }
+    }
+
+    /// Returns an `AllocRequest` for growing this `IdPool`.
+    #[inline]
+    pub fn grow_alloc(&self) -> AllocRequest {
+        AllocRequest {
+            nbits: self.map.len() << 1,
+        }
+    }
+
+    /// Grows pool by using a new `Bitmap`, if still necessary.
+    #[inline]
+    pub fn grow(&mut self, mut resizer: PoolResizer) {
+        // `resizer` bitmap might have been allocated without locks,
+        // so this call could now be outdated. In this case, drop
+        // `resizer` and move on.
+        if resizer.new.len() <= self.map.len() {
+            return;
+        }
+
+        resizer.new.copy_and_extend(&self.map);
+        self.map = resizer.new;
+    }
+
+    /// Acquires a new ID by finding and setting the next zero bit in the
+    /// bitmap. Upon success, returns its index. Otherwise, returns `None`
+    /// to indicate that a `grow_alloc` is needed.
+    #[inline]
+    pub fn acquire_next_id(&mut self, offset: usize) -> Option<usize> {
+        match self.map.next_zero_bit(offset) {
+            res @ Some(nr) => {
+                self.map.set_bit(nr);
+                res
+            }
+            None => None,
+        }
+    }
+
+    /// Releases an ID.
+    #[inline]
+    pub fn release_id(&mut self, id: usize) {
+        self.map.clear_bit(id);
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index 9f675c0841e6..d77a27bee388 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -51,6 +51,7 @@
 #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)]
 pub mod firmware;
 pub mod fs;
+pub mod id_pool;
 pub mod init;
 pub mod io;
 pub mod ioctl;
-- 
2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 0/4] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Fri, Mar 21, 2025 at 11:15:28AM +0000, Burak Emir wrote:
> This series adds a Rust bitmap API for porting the approach from 
> commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> 
> The Rust bitmap API provides a safe abstraction to underlying bitmap
> and bitops operations. For now, only includes method necessary for 
> dbitmap.h, more can be added later. We perform bounds checks for 
> hardening, violations are programmer errors that result in panics.
> 
> This version includes an optimization to represent the bitmap inline,
> as suggested by Yury.

We have a tag for it:

Suggested-by: Yury Norov <yury.norov@gmail.com>
 
> The Rust equivalent of dbitmap.h is included as id_pool.rs, which is
> tightly coupled to the bitmap API. Includes an example of usage
> that requires releasing a spinlock, as expected in Binder driver.

I don't think it's worth to refer the existing dbitmap.h, because:

1. It's buggy;
2. You limit yourself with committing to provide an 'equivalent' API.
3. If you want to bring the existing dbitmaps.h, you'd just bring
   bindings for them, not a re-implementation.

Can you just say that you're adding dynamic bit arrays in rust?

> This is v5 of a patch introducing Rust bitmap API [v4]. Thanks
> for all the helpful comments, this series has improved significantly
> as a result of your work.
> 
> Changes v4 --> v5: (suggested by Yury and Alice)
> - rebased on next-20250318
> - split MAINTAINERS changes
> - no dependencies on [1] and [2] anymore - Viresh,
>   please do add a separate section if you want to maintain cpumask.rs
>   separately.
> - imports atomic and non-atomic variants, introduces a naming convention
>   set_bit and set_bit_atomic on the Rust side.
> - changed naming and comments. Keeping `new`.
> - change dynamic_id_pool to id_pool
> - represent bitmap inline when possible
> - add some more tests
> - add bqe@google.com as M: for the Rust abstractions

Instead of 'bqe@google.com' just say: myself.

Thanks,
Yury

Re: [PATCH v5 3/4] rust: add bitmap API.

[Yury Norov]

On Fri, Mar 21, 2025 at 11:15:31AM +0000, Burak Emir wrote:
> Provides an abstraction for C bitmap API and bitops operations.
> Includes enough to implement a Binder data structure that was
> introduced in commit 15d9da3f818c ("binder: use bitmap for faster
> descriptor lookup"), namely drivers/android/dbitmap.h.
> 
> The implementation is optimized to represent the bitmap inline
> if it would take the space of a pointer. This saves allocations.
> We offer a safe API through bounds checks which panic if violated.
> 
> We use the `usize` type for sizes and indices into the bitmap,
> because Rust generally always uses that type for indices and lengths
> and it will be more convenient if the API accepts that type. This means
> that we need to perform some casts to/from u32 and usize, since the C
> headers use unsigned int instead of size_t/unsigned long for these
> numbers in some places.
> 
> Adds new MAINTAINERS section BITMAP API [RUST].
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
>  MAINTAINERS           |   7 +
>  rust/kernel/bitmap.rs | 293 ++++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs    |   1 +
>  3 files changed, 301 insertions(+)
>  create mode 100644 rust/kernel/bitmap.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 7cd15c25a43c..bc8f05431689 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4114,6 +4114,13 @@ S:	Maintained
>  F:	rust/helpers/bitmap.c
>  F:	rust/helpers/cpumask.c
>  
> +BITMAP API [RUST]
> +M:	Alice Ryhl <aliceryhl@google.com>
> +M:	Burak Emir <bqe@google.com>
> +R:	Yury Norov <yury.norov@gmail.com>
> +S:	Maintained
> +F:	rust/kernel/bitmap.rs
> +
>  BITOPS API
>  M:	Yury Norov <yury.norov@gmail.com>
>  R:	Rasmus Villemoes <linux@rasmusvillemoes.dk>
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> new file mode 100644
> index 000000000000..118dceaf2b4b
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,293 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +// Copyright (C) 2025 Google LLC.
> +
> +//! Rust API for bitmap.
> +//!
> +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
> +
> +use crate::alloc::{AllocError, Flags};
> +use crate::bindings;
> +use core::ptr::NonNull;
> +
> +/// Holds either a pointer to array of `unsigned long` or a small bitmap.
> +#[repr(C)]
> +union BitmapRepr {
> +  bitmap: usize,
> +  ptr: NonNull<usize>
> +}
> +
> +/// Represents a bitmap.
> +///
> +/// Wraps underlying C bitmap API.
> +///
> +/// # Examples
> +///
> +/// Basic usage
> +///
> +/// ```
> +/// use kernel::alloc::flags::GFP_KERNEL;
> +/// use kernel::bitmap::Bitmap;
> +///
> +/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
> +/// assert_eq!(16, b.len());
> +/// for i in 0..16 {
> +///   if i % 4 == 0 {
> +///     b.set_bit(i);
> +///   }
> +/// }

In C we separate declarations from function body with an empty line.
Can you do that in rust? Can you point to a rust coding style? Do you
guys really use 2-whitespace tabs?

> +/// assert_eq!(Some(1), b.next_zero_bit(0));
> +/// assert_eq!(Some(5), b.next_zero_bit(5));
> +/// assert_eq!(Some(12), b.last_bit());
> +/// # Ok::<(), Error>(())
> +/// ```

I think I already asked to make the test a separate unit. It's amazing
that rust understands scattered commented blocks of code and can turn
them into unit tests. Unfortunately, I'm not.

Please create a separate unit and test everything there, just like we
do with normal C code.

For find_bit functions we have a lib/find_bit_benchmark.c Can you add
a similar rust test, so we'll make sure you're not introducing
performance regressions with your wrappers?

Please don't use KUNITs. It's not ready for benchmarks, and tests built
against it don't run on major distros.

> +///
> +/// Requesting too large values results in [`AllocError`]
> +///
> +/// ```
> +/// use kernel::alloc::flags::GFP_KERNEL;
> +/// use kernel::bitmap::Bitmap;
> +/// assert!(Bitmap::new(1 << 31, GFP_KERNEL).is_err());
> +/// ```
> +///
> +/// # Invariants
> +///
> +/// * `nbits` is `<= i32::MAX - 1` and never changes.

Undershoot this time. It's exactly i32::MAX.

> +/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a bitmap.
> +/// * otherwise, `repr` holds a non-null pointer that was obtained from a
> +///   successful call to `bitmap_zalloc` and holds the address of an initialized
> +///   array of `unsigned long` that is large enough to hold `nbits` bits.

Are you sure a public method description should bear implementation
details? I'm not. If implementation changes in future, the public API
should stay stable (yes, including comments).

> +pub struct Bitmap {
> +    /// Representation of bitmap.
> +    repr: BitmapRepr,
> +    /// Length of this bitmap. Must be `<= i32::MAX - 1`.
> +    nbits: usize,
> +}
> +
> +impl Drop for Bitmap {
> +    fn drop(&mut self) {
> +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            return
> +        }
> +        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
> +        //
> +        // INVARIANT: there is no other use of the `self.ptr` after this
> +        // call and the value is being dropped so the broken invariant is
> +        // not observable on function exit.
> +        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
> +    }
> +}
> +
> +impl Bitmap {
> +    /// Constructs a new [`Bitmap`].
> +    ///
> +    /// If the length `nbits` is small enough to admit inline representation, this

The "length nbits" is a tautology.

> +    /// implementation does not allocate.
> +    ///
> +    /// Fails with [`AllocError`] when the [`Bitmap`] could not be allocated. This
> +    /// includes the case when `nbits` is greater than `i32::MAX - 1`.
> +    #[inline]
> +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> +        if nbits <= bindings::BITS_PER_LONG as _ {
> +            return Ok(Bitmap { repr: BitmapRepr { bitmap: 0 }, nbits });
> +        }
> +        if nbits <= i32::MAX.try_into().unwrap() {

OK, I'm not a rust professional, but I have a serious question: is
this method chain the simplest way to compare two numbers?

> +            let nbits_u32 = u32::try_from(nbits).unwrap();
> +            // SAFETY: `nbits <= i32::MAX - 1` and the C function handles `nbits == 0`.
> +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> +            // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
> +            return Ok(Bitmap {
> +                repr: BitmapRepr { ptr },
> +                nbits,
> +            });
> +        }
> +        Err(AllocError)

Can you revert the logic and save indentation level?

> +    }
> +
> +    /// Returns length of this [`Bitmap`].
> +    #[inline]
> +    pub fn len(&self) -> usize {
> +        self.nbits
> +    }
> +
> +    /// Returns a mutable raw pointer to the backing [`Bitmap`].
> +    #[inline]
> +    fn as_mut_ptr(&mut self) -> *mut usize {
> +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            // SAFETY: Bitmap is represented inline.
> +            unsafe { core::ptr::addr_of_mut!(self.repr.bitmap) }
> +        } else {
> +            // SAFETY: Bitmap is represented as array of `unsigned long`.
> +            unsafe { self.repr.ptr.as_mut() }
> +        }
> +    }
> +
> +    /// Returns a raw pointer to the backing [`Bitmap`].
> +    #[inline]
> +    fn as_ptr(&self) -> *const usize {
> +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            // SAFETY: Bitmap is represented inline.
> +            unsafe { core::ptr::addr_of!(self.repr.bitmap) }
> +        } else {
> +            // SAFETY: Bitmap is represented as array of `unsigned long`.
> +            unsafe { self.repr.ptr.as_ptr() }
> +        }
> +    }
> +
> +    /// Set bit with index `index`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn set_bit(&mut self, index: usize) {
> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: Bit `index` is within bounds.
> +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Set bit with index `index`, atomically.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.

I think we agreed that if you decide to change set_bit() notation from
atomic to non-atomic, you'll add a beefy paragraph explaining your
choice. Please do so. Please prepend your paragraph with an ATTENTION!
or even WARNING! eye-catcher. Please describe it in cover-letter, commit
message and here, right in the source code. 

Is there any mechanism in rust to enforce the rule: set_bit_atomic() is
never for more than once in a raw on the same bitmap, or together with
a non-atomic bitmap function, like dbitmap.h does? C lacks for it desperately.

> +    #[inline]
> +    pub fn set_bit_atomic(&self, index: usize) {
> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: `index` is within bounds and `set_bit` is atomic.
> +        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
> +    }
> +
> +    /// Clear bit with index `index`.

Index 'index' is also a tautology. Can you just say:
        Clear 'index' bit

> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn clear_bit(&mut self, index: usize) {
> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: `index` is within bounds.
> +        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Clear bit with index `index`, atomically.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn clear_bit_atomic(&self, index: usize) {
> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: `index` is within bounds and `clear_bit` is atomic.
> +        unsafe { bindings::clear_bit(index as u32, self.as_ptr() as *mut usize) };
> +    }
> +
> +    /// Copy `src` into this [`Bitmap`] and set any remaining bits to zero.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> +    /// assert_eq!(None, long_bitmap.last_bit());
> +    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> +    /// short_bitmap.set_bit(7);
> +    ///
> +    /// long_bitmap.copy_and_extend(&short_bitmap);
> +    /// assert_eq!(Some(7), long_bitmap.last_bit());
> +    ///
> +    /// long_bitmap.clear_bit(7);
> +    /// assert_eq!(None, long_bitmap.last_bit());
> +    ///
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn copy_and_extend(&mut self, src: &Bitmap) {
> +        let len = core::cmp::min(src.nbits, self.nbits);
> +        // SAFETY: access to `self` and `src` is within bounds.
> +        unsafe {
> +            bindings::bitmap_copy_and_extend(
> +                self.as_mut_ptr(),
> +                src.as_ptr(),
> +                len as u32,
> +                self.nbits as u32,
> +            )
> +        };
> +    }
> +
> +    /// Finds last bit that is set.

Find last set bit, please.

> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let bitmap = Bitmap::new(64, GFP_KERNEL)?;
> +    /// match bitmap.last_bit() {
> +    ///     Some(idx) => {
> +    ///         pr_info!("The last bit has index {idx}.\n");
> +    ///     }
> +    ///     None => {
> +    ///         pr_info!("All bits in this bitmap are 0.\n");
> +    ///     }
> +    /// }
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn last_bit(&self) -> Option<usize> {
> +        // SAFETY: `nbits == 0` is supported and access is within bounds.
> +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> +        if index == self.nbits {
> +            None
> +        } else {
> +            Some(index)
> +        }
> +    }
> +
> +    /// Finds next zero bit, starting from `start`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
> +        assert!(
> +            start < self.nbits,
> +            "Offset `start` must be < {}, was {}",

The 'offset' and 'start' here are the same. You can use just 'start'.
Are you sure that rust printing function will handle backquotes properly?

I'm not sure that every user of bitmaps should panic if he goes out of
boundaries. If your assert() is similar to WARN_ON() or BUG_ON(), it's
wrong. You can do that in client code, but not in a generic library.
(Except for hardening reasons under a corresponding config.)

for_each_set_bitrange() is an example where offset >= nbits is an
expected and normal behavior.

> +            self.nbits,
> +            start
> +        );
> +
> +        // SAFETY: access is within bounds.
> +        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, start) };
> +        if index == self.nbits {
> +            None
> +        } else {
> +            Some(index)
> +        }
> +    }
> +}
> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index 6b46bc481d94..9f675c0841e6 100644
> --- a/rust/kernel/lib.rs
> +++ b/rust/kernel/lib.rs
> @@ -36,6 +36,7 @@
>  pub use ffi;
>  
>  pub mod alloc;
> +pub mod bitmap;
>  #[cfg(CONFIG_BLOCK)]
>  pub mod block;
>  #[doc(hidden)]
> -- 
> 2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 2/4] rust: add bindings for bitops.h

[Yury Norov]

On Fri, Mar 21, 2025 at 11:15:30AM +0000, Burak Emir wrote:
> Makes atomic set_bit and clear_bit inline functions as well as the
> non-atomic variants __set_bit and __clear_bit available to Rust.
> Adds a new MAINTAINERS section BITOPS API BINDINGS [RUST].
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
>  MAINTAINERS            |  5 +++++
>  rust/helpers/bitops.c  | 23 +++++++++++++++++++++++
>  rust/helpers/helpers.c |  1 +
>  3 files changed, 29 insertions(+)
>  create mode 100644 rust/helpers/bitops.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 52fc47a28b4c..7cd15c25a43c 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4128,6 +4128,11 @@ F:	include/linux/bitops.h
>  F:	lib/test_bitops.c
>  F:	tools/*/bitops*
>  
> +BITOPS API BINDINGS [RUST]
> +M:	Yury Norov <yury.norov@gmail.com>
> +S:	Maintained
> +F:	rust/helpers/bitops.c
> +
>  BLINKM RGB LED DRIVER
>  M:	Jan-Simon Moeller <jansimon.moeller@gmx.de>
>  S:	Maintained
> diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c
> new file mode 100644
> index 000000000000..2eaab292db4f
> --- /dev/null
> +++ b/rust/helpers/bitops.c
> @@ -0,0 +1,23 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bitops.h>
> +
> +void rust_helper___set_bit(unsigned int nr, unsigned long *addr)
> +{
> +	__set_bit(nr, addr);
> +}
> +
> +void rust_helper___clear_bit(unsigned int nr, unsigned long *addr)
> +{
> +	__clear_bit(nr, addr);
> +}
> +
> +void rust_helper_set_bit(unsigned int nr, unsigned long *addr)

volatile

> +{
> +	set_bit(nr, addr);
> +}
> +
> +void rust_helper_clear_bit(unsigned int nr, unsigned long *addr)
> +{
> +	clear_bit(nr, addr);
> +}
> diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
> index d4a60f1d6cc4..0c25cc86a52a 100644
> --- a/rust/helpers/helpers.c
> +++ b/rust/helpers/helpers.c
> @@ -8,6 +8,7 @@
>   */
>  
>  #include "bitmap.c"
> +#include "bitops.c"
>  #include "blk.c"
>  #include "bug.c"
>  #include "build_assert.c"
> -- 
> 2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 4/4] rust: add dynamic ID pool abstraction for bitmap

[Yury Norov]

On Fri, Mar 21, 2025 at 11:15:32AM +0000, Burak Emir wrote:
> This is a port of the Binder data structure introduced in commit
> 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> Rust.
> 
> Like drivers/android/dbitmap.h, the ID pool abstraction lets
> clients acquire and release IDs. The implementation uses a bitmap to
> know what IDs are in use, and gives clients fine-grained control over
> the time of allocation. This fine-grained control is needed in the
> Android Binder. We provide an example that release a spinlock for
> allocation and unit tests (rustdoc examples).
> 
> The implementation is not aware that the underlying Bitmap abstraction
> handles lengths below BITS_PER_LONG without allocation.
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>

Before I'll dig into this, can you describe the usecase? Is this just
a dynamic array of bits, or something more unusual? What's your desired
complexity for an acquire_id() - O(n) strictly, or amortized? Are you
going to use it in IRQ or similar restricted contexts?

> ---
>  MAINTAINERS            |   1 +
>  rust/kernel/id_pool.rs | 201 +++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs     |   1 +
>  3 files changed, 203 insertions(+)
>  create mode 100644 rust/kernel/id_pool.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index bc8f05431689..61ac5da0dfbf 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4120,6 +4120,7 @@ M:	Burak Emir <bqe@google.com>
>  R:	Yury Norov <yury.norov@gmail.com>
>  S:	Maintained
>  F:	rust/kernel/bitmap.rs
> +F:	rust/kernel/id_pool.rs
>  
>  BITOPS API
>  M:	Yury Norov <yury.norov@gmail.com>
> diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> new file mode 100644
> index 000000000000..8f07526bb580
> --- /dev/null
> +++ b/rust/kernel/id_pool.rs
> @@ -0,0 +1,201 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +// Copyright (C) 2025 Google LLC.
> +
> +//! Rust API for an ID pool backed by a `Bitmap`.
> +
> +use crate::alloc::{AllocError, Flags};
> +use crate::bitmap::Bitmap;
> +
> +/// Represents a dynamic ID pool backed by a `Bitmap`.
> +///
> +/// Clients acquire and release IDs from zero bits in a bitmap.
> +///
> +/// The ID pool can grow or shrink as needed. It has been designed
> +/// to support the scenario where users need to control the time
> +/// of allocation of a new backing bitmap, which may require release
> +/// of locks.
> +/// These operations then, are verified to determine if the grow or
> +/// shrink is sill valid.
> +///
> +/// # Examples
> +///
> +/// Basic usage
> +///
> +/// ```
> +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +/// use kernel::id_pool::IdPool;
> +///
> +/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
> +/// for i in 0..64 {
> +///   assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
> +/// }
> +///
> +/// pool.release_id(23);
> +/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
> +///
> +/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
> +/// let resizer = pool.grow_alloc().alloc(GFP_KERNEL)?;
> +/// pool.grow(resizer);
> +///
> +/// assert_eq!(pool.acquire_next_id(0), Some(64));
> +/// # Ok::<(), Error>(())
> +/// ```
> +///
> +/// Releasing spinlock to grow the pool
> +///
> +/// ```no_run
> +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +/// use kernel::sync::{new_spinlock, SpinLock};
> +/// use kernel::id_pool::IdPool;
> +///
> +/// fn get_id_maybe_alloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
> +///   let mut pool = guarded_pool.lock();
> +///   loop {
> +///     match pool.acquire_next_id(0) {
> +///       Some(index) => return Ok(index),
> +///       None => {
> +///         let alloc_request = pool.grow_alloc();
> +///         drop(pool);
> +///         let resizer = alloc_request.alloc(GFP_KERNEL)?;
> +///         pool = guarded_pool.lock();
> +///         pool.grow(resizer)
> +///       }
> +///     }
> +///   }
> +/// }
> +/// ```
> +pub struct IdPool {
> +    map: Bitmap,
> +}
> +
> +/// Returned when the `IdPool` should change size.
> +pub struct AllocRequest {
> +    nbits: usize,
> +}
> +
> +/// Contains an allocated `Bitmap` for resizing `IdPool`.
> +pub struct PoolResizer {
> +    new: Bitmap,
> +}
> +
> +impl AllocRequest {
> +    /// Allocates a new `Bitmap` for `IdPool`.
> +    pub fn alloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
> +        let new = Bitmap::new(self.nbits, flags)?;
> +        Ok(PoolResizer { new })
> +    }
> +}
> +
> +impl IdPool {
> +    /// Constructs a new `[IdPool]`.
> +    #[inline]
> +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> +        let map = Bitmap::new(nbits, flags)?;
> +        Ok(Self { map })
> +    }
> +
> +    /// Returns how many IDs this pool can currently have.
> +    #[inline]
> +    pub fn len(&self) -> usize {
> +        self.map.len()
> +    }
> +
> +    /// Returns an [`AllocRequest`] if the [`IdPool`] can be shrunk, [`None`] otherwise.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::id_pool::{AllocRequest, IdPool};
> +    ///
> +    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
> +    /// let alloc_request = pool.shrink_alloc().ok_or(AllocError)?;
> +    /// let resizer = alloc_request.alloc(GFP_KERNEL)?;
> +    /// pool.shrink(resizer);
> +    /// assert_eq!(pool.len(), kernel::bindings::BITS_PER_LONG as usize);
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
> +        let len = self.map.len();
> +        if len <= bindings::BITS_PER_LONG as usize {
> +            return None;
> +        }
> +        /*
> +         * Determine if the bitmap can shrink based on the position of
> +         * its last set bit. If the bit is within the first quarter of
> +         * the bitmap then shrinking is possible. In this case, the
> +         * bitmap should shrink to half its current size.
> +         */
> +        match self.map.last_bit() {
> +            Some(bit) => {
> +                if bit < (len >> 2) {
> +                    Some(AllocRequest { nbits: len >> 1 })
> +                } else {
> +                    None
> +                }
> +            }
> +            None => Some(AllocRequest {
> +                nbits: bindings::BITS_PER_LONG as usize,
> +            }),
> +        }
> +    }
> +
> +    /// Shrinks pool by using a new `Bitmap`, if still possible.
> +    #[inline]
> +    pub fn shrink(&mut self, mut resizer: PoolResizer) {
> +        // Verify that shrinking is still possible. The `resizer`
> +        // bitmap might have been allocated without locks, so this call
> +        // could now be outdated. In this case, drop `resizer` and move on.
> +        if let Some(AllocRequest { nbits }) = self.shrink_alloc() {
> +            if nbits <= resizer.new.len() {
> +                resizer.new.copy_and_extend(&self.map);
> +                self.map = resizer.new;
> +                return;
> +            }
> +        }
> +    }
> +
> +    /// Returns an `AllocRequest` for growing this `IdPool`.
> +    #[inline]
> +    pub fn grow_alloc(&self) -> AllocRequest {
> +        AllocRequest {
> +            nbits: self.map.len() << 1,
> +        }
> +    }
> +
> +    /// Grows pool by using a new `Bitmap`, if still necessary.
> +    #[inline]
> +    pub fn grow(&mut self, mut resizer: PoolResizer) {
> +        // `resizer` bitmap might have been allocated without locks,
> +        // so this call could now be outdated. In this case, drop
> +        // `resizer` and move on.
> +        if resizer.new.len() <= self.map.len() {
> +            return;
> +        }
> +
> +        resizer.new.copy_and_extend(&self.map);
> +        self.map = resizer.new;
> +    }
> +
> +    /// Acquires a new ID by finding and setting the next zero bit in the
> +    /// bitmap. Upon success, returns its index. Otherwise, returns `None`
> +    /// to indicate that a `grow_alloc` is needed.
> +    #[inline]
> +    pub fn acquire_next_id(&mut self, offset: usize) -> Option<usize> {
> +        match self.map.next_zero_bit(offset) {
> +            res @ Some(nr) => {
> +                self.map.set_bit(nr);
> +                res
> +            }
> +            None => None,
> +        }
> +    }
> +
> +    /// Releases an ID.
> +    #[inline]
> +    pub fn release_id(&mut self, id: usize) {
> +        self.map.clear_bit(id);
> +    }
> +}
> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index 9f675c0841e6..d77a27bee388 100644
> --- a/rust/kernel/lib.rs
> +++ b/rust/kernel/lib.rs
> @@ -51,6 +51,7 @@
>  #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)]
>  pub mod firmware;
>  pub mod fs;
> +pub mod id_pool;
>  pub mod init;
>  pub mod io;
>  pub mod ioctl;
> -- 
> 2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 3/4] rust: add bitmap API.

[Miguel Ojeda]

Hi Yury,

A couple comments in case it helps regarding the docs/comments discussion...

On Fri, Mar 21, 2025 at 5:04 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> In C we separate declarations from function body with an empty line.
> Can you do that in rust? Can you point to a rust coding style? Do you
> guys really use 2-whitespace tabs?

Please see https://docs.kernel.org/rust/coding-guidelines.html.

You are right that the example block you quoted should have the
formatting fixed.

I am not sure what you mean by separating declarations from body here.
I guess you mean variable declarations in C vs. the rest of the body
-- in Rust it is not done, i.e. declaring new bindings in the middle
as they are needed is expected (and sometimes needed).

> I think I already asked to make the test a separate unit. It's amazing
> that rust understands scattered commented blocks of code and can turn
> them into unit tests. Unfortunately, I'm not.
>
> Please create a separate unit and test everything there, just like we
> do with normal C code.

APIs should have examples, ideally good ones etc. The above looks like
an standard example, but maybe I am missing something.

The examples are meant to be documentation first and foremost, that
happens to double as a test (so that it does not get out of sync
etc.). It is how we document everything else in Rust, and in fact we
are becoming stricter in requesting more examples when people add more
APIs (otherwise they never get added :)

If actual tests are needed (i.e. on top of what examples provide),
then we just finally landed in -next `#[test]`-like support, i.e. unit
tests that can be written separately. We try to have tests as close as
possible to the code they exercise, too, but in some cases it may be
best to separate them (e.g. if there are way too many).

> For find_bit functions we have a lib/find_bit_benchmark.c Can you add
> a similar rust test, so we'll make sure you're not introducing
> performance regressions with your wrappers?
>
> Please don't use KUNITs. It's not ready for benchmarks, and tests built
> against it don't run on major distros.

Cc'ing David here in case he has more context around this...

I agree having a good "integrated benchmark" system would be nice, and
being able to mark particular "tests" as benchmarks etc.

Regarding distributions, it sounds an orthogonal issue to me, but I
may be lacking context...

> Are you sure a public method description should bear implementation
> details? I'm not. If implementation changes in future, the public API
> should stay stable (yes, including comments).

To clarify, it is describing the invariants of a type (i.e. it is not
a method description).

The invariants in some cases refer to private details (e.g. typically
a field), and whether to allow that or not is something we discussed
several times in the past.

We went with allowing the `# Invariants` section to refer to the
fields of a type if needed, as a practical decision. However, if
something is a "private invariant" that others must not rely on, then
we should still point it out explicitly etc.

I hope that clarifies.

Cheers,
Miguel

Re: [PATCH v5 0/4] rust: adds Bitmap API, ID pool and bindings

[Burak Emir]

On Fri, Mar 21, 2025 at 3:31 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Fri, Mar 21, 2025 at 11:15:28AM +0000, Burak Emir wrote:
> > This series adds a Rust bitmap API for porting the approach from
> > commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup")
> > to Rust. The functionality in dbitmap.h makes use of bitmap and bitops.
> >
> > The Rust bitmap API provides a safe abstraction to underlying bitmap
> > and bitops operations. For now, only includes method necessary for
> > dbitmap.h, more can be added later. We perform bounds checks for
> > hardening, violations are programmer errors that result in panics.
> >
> > This version includes an optimization to represent the bitmap inline,
> > as suggested by Yury.
>
> We have a tag for it:
>
> Suggested-by: Yury Norov <yury.norov@gmail.com>

Will add.

>
> > The Rust equivalent of dbitmap.h is included as id_pool.rs, which is
> > tightly coupled to the bitmap API. Includes an example of usage
> > that requires releasing a spinlock, as expected in Binder driver.
>
> I don't think it's worth to refer the existing dbitmap.h, because:
>
> 1. It's buggy;
> 2. You limit yourself with committing to provide an 'equivalent' API.
> 3. If you want to bring the existing dbitmaps.h, you'd just bring
>    bindings for them, not a re-implementation.
>
> Can you just say that you're adding dynamic bit arrays in rust?
>

True, "equivalent" is maybe too strong.

I considered "DybamicBitmap" but dbitmap is only providing a
dynamically sized bitmap under the hood (and with a specific API).
It does not expose `set_bit`, `clear_bit` methods as one would expect
from a Bitmap API.

That is why I found IdPool a better name. I am not attached to the
name, just dynamic bitmap seems misleading.
It is essentially a dynamically sized thing that happens to be
implemented efficiently using a bitmap.
I will leave it to Alice to explain why Binder needs it.


> > This is v5 of a patch introducing Rust bitmap API [v4]. Thanks
> > for all the helpful comments, this series has improved significantly
> > as a result of your work.
> >
> > Changes v4 --> v5: (suggested by Yury and Alice)
> > - rebased on next-20250318
> > - split MAINTAINERS changes
> > - no dependencies on [1] and [2] anymore - Viresh,
> >   please do add a separate section if you want to maintain cpumask.rs
> >   separately.
> > - imports atomic and non-atomic variants, introduces a naming convention
> >   set_bit and set_bit_atomic on the Rust side.
> > - changed naming and comments. Keeping `new`.
> > - change dynamic_id_pool to id_pool
> > - represent bitmap inline when possible
> > - add some more tests
> > - add bqe@google.com as M: for the Rust abstractions
>
> Instead of 'bqe@google.com' just say: myself.

Sure thing : )

Thanks,
Burak

Re: [PATCH v5 4/4] rust: add dynamic ID pool abstraction for bitmap

[Burak Emir]

On Fri, Mar 21, 2025 at 5:34 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Fri, Mar 21, 2025 at 11:15:32AM +0000, Burak Emir wrote:
> > This is a port of the Binder data structure introduced in commit
> > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > Rust.
> >
> > Like drivers/android/dbitmap.h, the ID pool abstraction lets
> > clients acquire and release IDs. The implementation uses a bitmap to
> > know what IDs are in use, and gives clients fine-grained control over
> > the time of allocation. This fine-grained control is needed in the
> > Android Binder. We provide an example that release a spinlock for
> > allocation and unit tests (rustdoc examples).
> >
> > The implementation is not aware that the underlying Bitmap abstraction
> > handles lengths below BITS_PER_LONG without allocation.
> >
> > Suggested-by: Alice Ryhl <aliceryhl@google.com>
> > Signed-off-by: Burak Emir <bqe@google.com>
>
> Before I'll dig into this, can you describe the usecase? Is this just
> a dynamic array of bits, or something more unusual? What's your desired
> complexity for an acquire_id() - O(n) strictly, or amortized? Are you
> going to use it in IRQ or similar restricted contexts?

Alice is probably the better person to answer. My rough summary of the
id pool use case is:
- In binder, there are these objects called nodes. Each node is owned
by one process.
- Nodes can exchange messages. This exchange can happen across
processes. There is a "first node" that sets up connections.
- Every process needs to manage ID to node mapping, which it does by
assigning (process-local) IDs.
 - In order to not exhaust ID space, ID numbers get reused.



> > ---
> >  MAINTAINERS            |   1 +
> >  rust/kernel/id_pool.rs | 201 +++++++++++++++++++++++++++++++++++++++++
> >  rust/kernel/lib.rs     |   1 +
> >  3 files changed, 203 insertions(+)
> >  create mode 100644 rust/kernel/id_pool.rs
> >
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index bc8f05431689..61ac5da0dfbf 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -4120,6 +4120,7 @@ M:      Burak Emir <bqe@google.com>
> >  R:   Yury Norov <yury.norov@gmail.com>
> >  S:   Maintained
> >  F:   rust/kernel/bitmap.rs
> > +F:   rust/kernel/id_pool.rs
> >
> >  BITOPS API
> >  M:   Yury Norov <yury.norov@gmail.com>
> > diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> > new file mode 100644
> > index 000000000000..8f07526bb580
> > --- /dev/null
> > +++ b/rust/kernel/id_pool.rs
> > @@ -0,0 +1,201 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +// Copyright (C) 2025 Google LLC.
> > +
> > +//! Rust API for an ID pool backed by a `Bitmap`.
> > +
> > +use crate::alloc::{AllocError, Flags};
> > +use crate::bitmap::Bitmap;
> > +
> > +/// Represents a dynamic ID pool backed by a `Bitmap`.
> > +///
> > +/// Clients acquire and release IDs from zero bits in a bitmap.
> > +///
> > +/// The ID pool can grow or shrink as needed. It has been designed
> > +/// to support the scenario where users need to control the time
> > +/// of allocation of a new backing bitmap, which may require release
> > +/// of locks.
> > +/// These operations then, are verified to determine if the grow or
> > +/// shrink is sill valid.
> > +///
> > +/// # Examples
> > +///
> > +/// Basic usage
> > +///
> > +/// ```
> > +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +/// use kernel::id_pool::IdPool;
> > +///
> > +/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
> > +/// for i in 0..64 {
> > +///   assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
> > +/// }
> > +///
> > +/// pool.release_id(23);
> > +/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
> > +///
> > +/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
> > +/// let resizer = pool.grow_alloc().alloc(GFP_KERNEL)?;
> > +/// pool.grow(resizer);
> > +///
> > +/// assert_eq!(pool.acquire_next_id(0), Some(64));
> > +/// # Ok::<(), Error>(())
> > +/// ```
> > +///
> > +/// Releasing spinlock to grow the pool
> > +///
> > +/// ```no_run
> > +/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +/// use kernel::sync::{new_spinlock, SpinLock};
> > +/// use kernel::id_pool::IdPool;
> > +///
> > +/// fn get_id_maybe_alloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
> > +///   let mut pool = guarded_pool.lock();
> > +///   loop {
> > +///     match pool.acquire_next_id(0) {
> > +///       Some(index) => return Ok(index),
> > +///       None => {
> > +///         let alloc_request = pool.grow_alloc();
> > +///         drop(pool);
> > +///         let resizer = alloc_request.alloc(GFP_KERNEL)?;
> > +///         pool = guarded_pool.lock();
> > +///         pool.grow(resizer)
> > +///       }
> > +///     }
> > +///   }
> > +/// }
> > +/// ```
> > +pub struct IdPool {
> > +    map: Bitmap,
> > +}
> > +
> > +/// Returned when the `IdPool` should change size.
> > +pub struct AllocRequest {
> > +    nbits: usize,
> > +}
> > +
> > +/// Contains an allocated `Bitmap` for resizing `IdPool`.
> > +pub struct PoolResizer {
> > +    new: Bitmap,
> > +}
> > +
> > +impl AllocRequest {
> > +    /// Allocates a new `Bitmap` for `IdPool`.
> > +    pub fn alloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
> > +        let new = Bitmap::new(self.nbits, flags)?;
> > +        Ok(PoolResizer { new })
> > +    }
> > +}
> > +
> > +impl IdPool {
> > +    /// Constructs a new `[IdPool]`.
> > +    #[inline]
> > +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> > +        let map = Bitmap::new(nbits, flags)?;
> > +        Ok(Self { map })
> > +    }
> > +
> > +    /// Returns how many IDs this pool can currently have.
> > +    #[inline]
> > +    pub fn len(&self) -> usize {
> > +        self.map.len()
> > +    }
> > +
> > +    /// Returns an [`AllocRequest`] if the [`IdPool`] can be shrunk, [`None`] otherwise.
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +    /// use kernel::id_pool::{AllocRequest, IdPool};
> > +    ///
> > +    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
> > +    /// let alloc_request = pool.shrink_alloc().ok_or(AllocError)?;
> > +    /// let resizer = alloc_request.alloc(GFP_KERNEL)?;
> > +    /// pool.shrink(resizer);
> > +    /// assert_eq!(pool.len(), kernel::bindings::BITS_PER_LONG as usize);
> > +    /// # Ok::<(), AllocError>(())
> > +    /// ```
> > +    #[inline]
> > +    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
> > +        let len = self.map.len();
> > +        if len <= bindings::BITS_PER_LONG as usize {
> > +            return None;
> > +        }
> > +        /*
> > +         * Determine if the bitmap can shrink based on the position of
> > +         * its last set bit. If the bit is within the first quarter of
> > +         * the bitmap then shrinking is possible. In this case, the
> > +         * bitmap should shrink to half its current size.
> > +         */
> > +        match self.map.last_bit() {
> > +            Some(bit) => {
> > +                if bit < (len >> 2) {
> > +                    Some(AllocRequest { nbits: len >> 1 })
> > +                } else {
> > +                    None
> > +                }
> > +            }
> > +            None => Some(AllocRequest {
> > +                nbits: bindings::BITS_PER_LONG as usize,
> > +            }),
> > +        }
> > +    }
> > +
> > +    /// Shrinks pool by using a new `Bitmap`, if still possible.
> > +    #[inline]
> > +    pub fn shrink(&mut self, mut resizer: PoolResizer) {
> > +        // Verify that shrinking is still possible. The `resizer`
> > +        // bitmap might have been allocated without locks, so this call
> > +        // could now be outdated. In this case, drop `resizer` and move on.
> > +        if let Some(AllocRequest { nbits }) = self.shrink_alloc() {
> > +            if nbits <= resizer.new.len() {
> > +                resizer.new.copy_and_extend(&self.map);
> > +                self.map = resizer.new;
> > +                return;
> > +            }
> > +        }
> > +    }
> > +
> > +    /// Returns an `AllocRequest` for growing this `IdPool`.
> > +    #[inline]
> > +    pub fn grow_alloc(&self) -> AllocRequest {
> > +        AllocRequest {
> > +            nbits: self.map.len() << 1,
> > +        }
> > +    }
> > +
> > +    /// Grows pool by using a new `Bitmap`, if still necessary.
> > +    #[inline]
> > +    pub fn grow(&mut self, mut resizer: PoolResizer) {
> > +        // `resizer` bitmap might have been allocated without locks,
> > +        // so this call could now be outdated. In this case, drop
> > +        // `resizer` and move on.
> > +        if resizer.new.len() <= self.map.len() {
> > +            return;
> > +        }
> > +
> > +        resizer.new.copy_and_extend(&self.map);
> > +        self.map = resizer.new;
> > +    }
> > +
> > +    /// Acquires a new ID by finding and setting the next zero bit in the
> > +    /// bitmap. Upon success, returns its index. Otherwise, returns `None`
> > +    /// to indicate that a `grow_alloc` is needed.
> > +    #[inline]
> > +    pub fn acquire_next_id(&mut self, offset: usize) -> Option<usize> {
> > +        match self.map.next_zero_bit(offset) {
> > +            res @ Some(nr) => {
> > +                self.map.set_bit(nr);
> > +                res
> > +            }
> > +            None => None,
> > +        }
> > +    }
> > +
> > +    /// Releases an ID.
> > +    #[inline]
> > +    pub fn release_id(&mut self, id: usize) {
> > +        self.map.clear_bit(id);
> > +    }
> > +}
> > diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> > index 9f675c0841e6..d77a27bee388 100644
> > --- a/rust/kernel/lib.rs
> > +++ b/rust/kernel/lib.rs
> > @@ -51,6 +51,7 @@
> >  #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)]
> >  pub mod firmware;
> >  pub mod fs;
> > +pub mod id_pool;
> >  pub mod init;
> >  pub mod io;
> >  pub mod ioctl;
> > --
> > 2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 3/4] rust: add bitmap API.

[Burak Emir]

On Fri, Mar 21, 2025 at 5:04 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Fri, Mar 21, 2025 at 11:15:31AM +0000, Burak Emir wrote:
> > Provides an abstraction for C bitmap API and bitops operations.
> > Includes enough to implement a Binder data structure that was
> > introduced in commit 15d9da3f818c ("binder: use bitmap for faster
> > descriptor lookup"), namely drivers/android/dbitmap.h.
> >
> > The implementation is optimized to represent the bitmap inline
> > if it would take the space of a pointer. This saves allocations.
> > We offer a safe API through bounds checks which panic if violated.
> >
> > We use the `usize` type for sizes and indices into the bitmap,
> > because Rust generally always uses that type for indices and lengths
> > and it will be more convenient if the API accepts that type. This means
> > that we need to perform some casts to/from u32 and usize, since the C
> > headers use unsigned int instead of size_t/unsigned long for these
> > numbers in some places.
> >
> > Adds new MAINTAINERS section BITMAP API [RUST].
> >
> > Suggested-by: Alice Ryhl <aliceryhl@google.com>
> > Signed-off-by: Burak Emir <bqe@google.com>
> > ---
> >  MAINTAINERS           |   7 +
> >  rust/kernel/bitmap.rs | 293 ++++++++++++++++++++++++++++++++++++++++++
> >  rust/kernel/lib.rs    |   1 +
> >  3 files changed, 301 insertions(+)
> >  create mode 100644 rust/kernel/bitmap.rs
> >
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index 7cd15c25a43c..bc8f05431689 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -4114,6 +4114,13 @@ S:     Maintained
> >  F:   rust/helpers/bitmap.c
> >  F:   rust/helpers/cpumask.c
> >
> > +BITMAP API [RUST]
> > +M:   Alice Ryhl <aliceryhl@google.com>
> > +M:   Burak Emir <bqe@google.com>
> > +R:   Yury Norov <yury.norov@gmail.com>
> > +S:   Maintained
> > +F:   rust/kernel/bitmap.rs
> > +
> >  BITOPS API
> >  M:   Yury Norov <yury.norov@gmail.com>
> >  R:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
> > diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> > new file mode 100644
> > index 000000000000..118dceaf2b4b
> > --- /dev/null
> > +++ b/rust/kernel/bitmap.rs
> > @@ -0,0 +1,293 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +// Copyright (C) 2025 Google LLC.
> > +
> > +//! Rust API for bitmap.
> > +//!
> > +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
> > +
> > +use crate::alloc::{AllocError, Flags};
> > +use crate::bindings;
> > +use core::ptr::NonNull;
> > +
> > +/// Holds either a pointer to array of `unsigned long` or a small bitmap.
> > +#[repr(C)]
> > +union BitmapRepr {
> > +  bitmap: usize,
> > +  ptr: NonNull<usize>
> > +}
> > +
> > +/// Represents a bitmap.
> > +///
> > +/// Wraps underlying C bitmap API.
> > +///
> > +/// # Examples
> > +///
> > +/// Basic usage
> > +///
> > +/// ```
> > +/// use kernel::alloc::flags::GFP_KERNEL;
> > +/// use kernel::bitmap::Bitmap;
> > +///
> > +/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
> > +/// assert_eq!(16, b.len());
> > +/// for i in 0..16 {
> > +///   if i % 4 == 0 {
> > +///     b.set_bit(i);
> > +///   }
> > +/// }
>
> In C we separate declarations from function body with an empty line.
> Can you do that in rust? Can you point to a rust coding style? Do you
> guys really use 2-whitespace tabs?

Fixed the indentation.

I assume you the line `let mut b = ...` declaration.
Added an empty line.

>
> > +/// assert_eq!(Some(1), b.next_zero_bit(0));
> > +/// assert_eq!(Some(5), b.next_zero_bit(5));
> > +/// assert_eq!(Some(12), b.last_bit());
> > +/// # Ok::<(), Error>(())
> > +/// ```
>
> I think I already asked to make the test a separate unit. It's amazing
> that rust understands scattered commented blocks of code and can turn
> them into unit tests. Unfortunately, I'm not.
>
> Please create a separate unit and test everything there, just like we
> do with normal C code.
>
> For find_bit functions we have a lib/find_bit_benchmark.c Can you add
> a similar rust test, so we'll make sure you're not introducing
> performance regressions with your wrappers?
>
> Please don't use KUNITs. It's not ready for benchmarks, and tests built
> against it don't run on major distros.
>

I will try out the Rust unit test infrastructure that Miguel mentioned
has landed.
Rust unit tests are in the same file.

I need to find out whether infrastructure exists for Rust benchmarks.

> > +///
> > +/// Requesting too large values results in [`AllocError`]
> > +///
> > +/// ```
> > +/// use kernel::alloc::flags::GFP_KERNEL;
> > +/// use kernel::bitmap::Bitmap;
> > +/// assert!(Bitmap::new(1 << 31, GFP_KERNEL).is_err());
> > +/// ```
> > +///
> > +/// # Invariants
> > +///
> > +/// * `nbits` is `<= i32::MAX - 1` and never changes.
>
> Undershoot this time. It's exactly i32::MAX.

Fixed

>
> > +/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a bitmap.
> > +/// * otherwise, `repr` holds a non-null pointer that was obtained from a
> > +///   successful call to `bitmap_zalloc` and holds the address of an initialized
> > +///   array of `unsigned long` that is large enough to hold `nbits` bits.
>
> Are you sure a public method description should bear implementation
> details? I'm not. If implementation changes in future, the public API
> should stay stable (yes, including comments).

This is a good point, but there is a conflict: it is an /// #
Invariants which helps makes sense of safety comments.
I believe this necessarily has to mention implementation detail.

Maybe this should be // comments instead of ///, but all existing code
uses /// # Invariants.
I'd appreciate some Rust-for-Linux guidance here, going to leave as is for now.

> > +pub struct Bitmap {
> > +    /// Representation of bitmap.
> > +    repr: BitmapRepr,
> > +    /// Length of this bitmap. Must be `<= i32::MAX - 1`.
> > +    nbits: usize,
> > +}
> > +
> > +impl Drop for Bitmap {
> > +    fn drop(&mut self) {
> > +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> > +            return
> > +        }
> > +        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
> > +        //
> > +        // INVARIANT: there is no other use of the `self.ptr` after this
> > +        // call and the value is being dropped so the broken invariant is
> > +        // not observable on function exit.
> > +        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
> > +    }
> > +}
> > +
> > +impl Bitmap {
> > +    /// Constructs a new [`Bitmap`].
> > +    ///
> > +    /// If the length `nbits` is small enough to admit inline representation, this
>
> The "length nbits" is a tautology.
>
> > +    /// implementation does not allocate.
> > +    ///
> > +    /// Fails with [`AllocError`] when the [`Bitmap`] could not be allocated. This
> > +    /// includes the case when `nbits` is greater than `i32::MAX - 1`.
> > +    #[inline]
> > +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> > +        if nbits <= bindings::BITS_PER_LONG as _ {
> > +            return Ok(Bitmap { repr: BitmapRepr { bitmap: 0 }, nbits });
> > +        }
> > +        if nbits <= i32::MAX.try_into().unwrap() {
>
> OK, I'm not a rust professional, but I have a serious question: is
> this method chain the simplest way to compare two numbers?

This is due to the different types: i32 and usize are different types.
As humans,
we can see that i32::MAX will be positive and fit into usize, and rustc will
figure this out during translation, but the type-system does not take ranges
into account and forces us to spell out a fallible conversion.

> > +            let nbits_u32 = u32::try_from(nbits).unwrap();
> > +            // SAFETY: `nbits <= i32::MAX - 1` and the C function handles `nbits == 0`.
> > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> > +            // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
> > +            return Ok(Bitmap {
> > +                repr: BitmapRepr { ptr },
> > +                nbits,
> > +            });
> > +        }
> > +        Err(AllocError)
>
> Can you revert the logic and save indentation level?

Done

> > +    }
> > +
> > +    /// Returns length of this [`Bitmap`].
> > +    #[inline]
> > +    pub fn len(&self) -> usize {
> > +        self.nbits
> > +    }
> > +
> > +    /// Returns a mutable raw pointer to the backing [`Bitmap`].
> > +    #[inline]
> > +    fn as_mut_ptr(&mut self) -> *mut usize {
> > +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> > +            // SAFETY: Bitmap is represented inline.
> > +            unsafe { core::ptr::addr_of_mut!(self.repr.bitmap) }
> > +        } else {
> > +            // SAFETY: Bitmap is represented as array of `unsigned long`.
> > +            unsafe { self.repr.ptr.as_mut() }
> > +        }
> > +    }
> > +
> > +    /// Returns a raw pointer to the backing [`Bitmap`].
> > +    #[inline]
> > +    fn as_ptr(&self) -> *const usize {
> > +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> > +            // SAFETY: Bitmap is represented inline.
> > +            unsafe { core::ptr::addr_of!(self.repr.bitmap) }
> > +        } else {
> > +            // SAFETY: Bitmap is represented as array of `unsigned long`.
> > +            unsafe { self.repr.ptr.as_ptr() }
> > +        }
> > +    }
> > +
> > +    /// Set bit with index `index`.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn set_bit(&mut self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: Bit `index` is within bounds.
> > +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> > +    }
> > +
> > +    /// Set bit with index `index`, atomically.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
>
> I think we agreed that if you decide to change set_bit() notation from
> atomic to non-atomic, you'll add a beefy paragraph explaining your
> choice. Please do so. Please prepend your paragraph with an ATTENTION!
> or even WARNING! eye-catcher. Please describe it in cover-letter, commit
> message and here, right in the source code.
>
> Is there any mechanism in rust to enforce the rule: set_bit_atomic() is
> never for more than once in a raw on the same bitmap, or together with
> a non-atomic bitmap function, like dbitmap.h does? C lacks for it desperately.

Oh, this is good point.

I considered making this unsafe - but it seems this is actually safe:

The argument for safety would be one of exclusive access:
- when one has a &mut reference, then there cannot be another thread
that can call set_bit_atomic or clear_bit_atomic.
- when multiple threads have shared referenced &bitmap, then they
cannot call non-atomic methods.


> > +    #[inline]
> > +    pub fn set_bit_atomic(&self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: `index` is within bounds and `set_bit` is atomic.
> > +        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
> > +    }
> > +
> > +    /// Clear bit with index `index`.
>
> Index 'index' is also a tautology. Can you just say:
>         Clear 'index' bit

Done.

> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn clear_bit(&mut self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: `index` is within bounds.
> > +        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
> > +    }
> > +
> > +    /// Clear bit with index `index`, atomically.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn clear_bit_atomic(&self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: `index` is within bounds and `clear_bit` is atomic.
> > +        unsafe { bindings::clear_bit(index as u32, self.as_ptr() as *mut usize) };
> > +    }
> > +
> > +    /// Copy `src` into this [`Bitmap`] and set any remaining bits to zero.
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +    /// use kernel::bitmap::Bitmap;
> > +    ///
> > +    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> > +    /// assert_eq!(None, long_bitmap.last_bit());
> > +    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> > +    /// short_bitmap.set_bit(7);
> > +    ///
> > +    /// long_bitmap.copy_and_extend(&short_bitmap);
> > +    /// assert_eq!(Some(7), long_bitmap.last_bit());
> > +    ///
> > +    /// long_bitmap.clear_bit(7);
> > +    /// assert_eq!(None, long_bitmap.last_bit());
> > +    ///
> > +    /// # Ok::<(), AllocError>(())
> > +    /// ```
> > +    #[inline]
> > +    pub fn copy_and_extend(&mut self, src: &Bitmap) {
> > +        let len = core::cmp::min(src.nbits, self.nbits);
> > +        // SAFETY: access to `self` and `src` is within bounds.
> > +        unsafe {
> > +            bindings::bitmap_copy_and_extend(
> > +                self.as_mut_ptr(),
> > +                src.as_ptr(),
> > +                len as u32,
> > +                self.nbits as u32,
> > +            )
> > +        };
> > +    }
> > +
> > +    /// Finds last bit that is set.
>
> Find last set bit, please.

Done

> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +    /// use kernel::bitmap::Bitmap;
> > +    ///
> > +    /// let bitmap = Bitmap::new(64, GFP_KERNEL)?;
> > +    /// match bitmap.last_bit() {
> > +    ///     Some(idx) => {
> > +    ///         pr_info!("The last bit has index {idx}.\n");
> > +    ///     }
> > +    ///     None => {
> > +    ///         pr_info!("All bits in this bitmap are 0.\n");
> > +    ///     }
> > +    /// }
> > +    /// # Ok::<(), AllocError>(())
> > +    /// ```
> > +    #[inline]
> > +    pub fn last_bit(&self) -> Option<usize> {
> > +        // SAFETY: `nbits == 0` is supported and access is within bounds.
> > +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> > +        if index == self.nbits {
> > +            None
> > +        } else {
> > +            Some(index)
> > +        }
> > +    }
> > +
> > +    /// Finds next zero bit, starting from `start`.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
> > +        assert!(
> > +            start < self.nbits,
> > +            "Offset `start` must be < {}, was {}",
>
> The 'offset' and 'start' here are the same. You can use just 'start'.
> Are you sure that rust printing function will handle backquotes properly?
>
Done. Backticks are not special in format strings.

> I'm not sure that every user of bitmaps should panic if he goes out of
> boundaries. If your assert() is similar to WARN_ON() or BUG_ON(), it's
> wrong. You can do that in client code, but not in a generic library.
> (Except for hardening reasons under a corresponding config.)

Yes we discussed this: it is purely for hardening reasons.

> for_each_set_bitrange() is an example where offset >= nbits is an
> expected and normal behavior.

Makes sense, but we could offer iteration in the Rust API without
permitting offset >= nbits in public methods.

> > +            self.nbits,
> > +            start
> > +        );
> > +
> > +        // SAFETY: access is within bounds.
> > +        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, start) };
> > +        if index == self.nbits {
> > +            None
> > +        } else {
> > +            Some(index)
> > +        }
> > +    }
> > +}
> > diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> > index 6b46bc481d94..9f675c0841e6 100644
> > --- a/rust/kernel/lib.rs
> > +++ b/rust/kernel/lib.rs
> > @@ -36,6 +36,7 @@
> >  pub use ffi;
> >
> >  pub mod alloc;
> > +pub mod bitmap;
> >  #[cfg(CONFIG_BLOCK)]
> >  pub mod block;
> >  #[doc(hidden)]
> > --
> > 2.49.0.395.g12beb8f557-goog

Re: [PATCH v5 3/4] rust: add bitmap API.

[Burak Emir]

On Fri, Mar 21, 2025 at 7:50 PM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> Hi Yury,
>
> A couple comments in case it helps regarding the docs/comments discussion...
>
> On Fri, Mar 21, 2025 at 5:04 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > In C we separate declarations from function body with an empty line.
> > Can you do that in rust? Can you point to a rust coding style? Do you
> > guys really use 2-whitespace tabs?
>
> Please see https://docs.kernel.org/rust/coding-guidelines.html.
>
> You are right that the example block you quoted should have the
> formatting fixed.
>
> I am not sure what you mean by separating declarations from body here.
> I guess you mean variable declarations in C vs. the rest of the body
> -- in Rust it is not done, i.e. declaring new bindings in the middle
> as they are needed is expected (and sometimes needed).
>
> > I think I already asked to make the test a separate unit. It's amazing
> > that rust understands scattered commented blocks of code and can turn
> > them into unit tests. Unfortunately, I'm not.
> >
> > Please create a separate unit and test everything there, just like we
> > do with normal C code.
>
> APIs should have examples, ideally good ones etc. The above looks like
> an standard example, but maybe I am missing something.
>
> The examples are meant to be documentation first and foremost, that
> happens to double as a test (so that it does not get out of sync
> etc.). It is how we document everything else in Rust, and in fact we
> are becoming stricter in requesting more examples when people add more
> APIs (otherwise they never get added :)
>
> If actual tests are needed (i.e. on top of what examples provide),
> then we just finally landed in -next `#[test]`-like support, i.e. unit
> tests that can be written separately. We try to have tests as close as
> possible to the code they exercise, too, but in some cases it may be
> best to separate them (e.g. if there are way too many).
>

I tried this in today's mainline and got errors "undefined reference
to `bitmap_free', `bitmap_zalloc`..."
Is the version that landed in -next fixing those? Are there known limitations?

> > For find_bit functions we have a lib/find_bit_benchmark.c Can you add
> > a similar rust test, so we'll make sure you're not introducing
> > performance regressions with your wrappers?
> >
> > Please don't use KUNITs. It's not ready for benchmarks, and tests built
> > against it don't run on major distros.
>
> Cc'ing David here in case he has more context around this...
>
> I agree having a good "integrated benchmark" system would be nice, and
> being able to mark particular "tests" as benchmarks etc.
>
> Regarding distributions, it sounds an orthogonal issue to me, but I
> may be lacking context...
>
> > Are you sure a public method description should bear implementation
> > details? I'm not. If implementation changes in future, the public API
> > should stay stable (yes, including comments).
>
> To clarify, it is describing the invariants of a type (i.e. it is not
> a method description).
>
> The invariants in some cases refer to private details (e.g. typically
> a field), and whether to allow that or not is something we discussed
> several times in the past.
>
> We went with allowing the `# Invariants` section to refer to the
> fields of a type if needed, as a practical decision. However, if
> something is a "private invariant" that others must not rely on, then
> we should still point it out explicitly etc.
>
> I hope that clarifies.

Thanks, it does & I will leave these as is then.

Re: [PATCH v5 3/4] rust: add bitmap API.

[David Gow]

[-- Attachment #1: Type: text/plain, Size: 3928 bytes --]

On Sat, 22 Mar 2025 at 02:50, Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> Hi Yury,
>
> A couple comments in case it helps regarding the docs/comments discussion...
>
> On Fri, Mar 21, 2025 at 5:04 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > In C we separate declarations from function body with an empty line.
> > Can you do that in rust? Can you point to a rust coding style? Do you
> > guys really use 2-whitespace tabs?
>
> Please see https://docs.kernel.org/rust/coding-guidelines.html.
>
> You are right that the example block you quoted should have the
> formatting fixed.
>
> I am not sure what you mean by separating declarations from body here.
> I guess you mean variable declarations in C vs. the rest of the body
> -- in Rust it is not done, i.e. declaring new bindings in the middle
> as they are needed is expected (and sometimes needed).
>
> > I think I already asked to make the test a separate unit. It's amazing
> > that rust understands scattered commented blocks of code and can turn
> > them into unit tests. Unfortunately, I'm not.
> >
> > Please create a separate unit and test everything there, just like we
> > do with normal C code.
>
> APIs should have examples, ideally good ones etc. The above looks like
> an standard example, but maybe I am missing something.
>
> The examples are meant to be documentation first and foremost, that
> happens to double as a test (so that it does not get out of sync
> etc.). It is how we document everything else in Rust, and in fact we
> are becoming stricter in requesting more examples when people add more
> APIs (otherwise they never get added :)
>
> If actual tests are needed (i.e. on top of what examples provide),
> then we just finally landed in -next `#[test]`-like support, i.e. unit
> tests that can be written separately. We try to have tests as close as
> possible to the code they exercise, too, but in some cases it may be
> best to separate them (e.g. if there are way too many).
>
> > For find_bit functions we have a lib/find_bit_benchmark.c Can you add
> > a similar rust test, so we'll make sure you're not introducing
> > performance regressions with your wrappers?
> >
> > Please don't use KUNITs. It's not ready for benchmarks, and tests built
> > against it don't run on major distros.
>
> Cc'ing David here in case he has more context around this...
>
> I agree having a good "integrated benchmark" system would be nice, and
> being able to mark particular "tests" as benchmarks etc.
>
> Regarding distributions, it sounds an orthogonal issue to me, but I
> may be lacking context...
>

Yeah: nothing has particularly changed here. KUnit is not aimed at
benchmarks specifically, and while it isn't impossible to get
something "benchmark-like" to work with it, it's definitely
suboptimal. And there aren't any immediate plans to add any more
benchmarking functionality to KUnit, though I'd be happy to hear any
proposals. :-)

If requiring CONFIG_KUNIT to be set (which, as mentioned in previous
discussions, is not the default on many distros) is a dealbreaker for
running tests, then of course that limits any tests to not using
KUnit. That being said, I suspect that supporting the "just build this
one test module against your existing kernel" case is going to be a
bit more of a pain here anyway, as it might end up depending on having
exactly the same toolchain/config/etc due to Rust's ABI not being
stable. (Am I missing anything here, Miguel?) And, of course, Rust's
built-in tests here would get automatically compiled down to KUnit
tests if enabled.

So, what I suspect you're looking for here is a separate module /
crate which benchmarks the bitmap type. With the way Rust crates are
laid out, I suspect this would need to live in a separate directory
and look something like samples/rust/rust_minimal.rs?

-- David

[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 5281 bytes --]

Re: [PATCH v5 3/4] rust: add bitmap API.

[Miguel Ojeda]

On Fri, Mar 28, 2025 at 9:51 AM David Gow <davidgow@google.com> wrote:
>
> KUnit. That being said, I suspect that supporting the "just build this
> one test module against your existing kernel" case is going to be a
> bit more of a pain here anyway, as it might end up depending on having
> exactly the same toolchain/config/etc due to Rust's ABI not being
> stable. (Am I missing anything here, Miguel?) And, of course, Rust's
> built-in tests here would get automatically compiled down to KUnit
> tests if enabled.

The ABI is not stable indeed, and modules need to be built with the
same toolchain.

> So, what I suspect you're looking for here is a separate module /
> crate which benchmarks the bitmap type. With the way Rust crates are
> laid out, I suspect this would need to live in a separate directory
> and look something like samples/rust/rust_minimal.rs?

Yeah, the module Yury mentioned seems like a normal one that calls
`ktime_get()` etc., so doing something like that in Rust should be
fine too.

But, yeah, I was thinking more in terms of having a proper framework
for those, rather than doing a custom thing per module and even having
those `ktime_get()` calls manually placed for every test etc.

Thanks for the context!

Cheers,
Miguel

Re: [PATCH v5 3/4] rust: add bitmap API.

[Burak Emir]

On Fri, Mar 28, 2025 at 10:06 AM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> On Fri, Mar 28, 2025 at 9:51 AM David Gow <davidgow@google.com> wrote:
> >
> > KUnit. That being said, I suspect that supporting the "just build this
> > one test module against your existing kernel" case is going to be a
> > bit more of a pain here anyway, as it might end up depending on having
> > exactly the same toolchain/config/etc due to Rust's ABI not being
> > stable. (Am I missing anything here, Miguel?) And, of course, Rust's
> > built-in tests here would get automatically compiled down to KUnit
> > tests if enabled.
>
> The ABI is not stable indeed, and modules need to be built with the
> same toolchain.
>
> > So, what I suspect you're looking for here is a separate module /
> > crate which benchmarks the bitmap type. With the way Rust crates are
> > laid out, I suspect this would need to live in a separate directory
> > and look something like samples/rust/rust_minimal.rs?
>
> Yeah, the module Yury mentioned seems like a normal one that calls
> `ktime_get()` etc., so doing something like that in Rust should be
> fine too.
>
> But, yeah, I was thinking more in terms of having a proper framework
> for those, rather than doing a custom thing per module and even having
> those `ktime_get()` calls manually placed for every test etc.
>

With Alice's help, I was able to add a find_bit_benchmark_rust module.
This was surprisingly straighforward. I will send out a version that
adds it right next to the find_bit_benchmark.c one, with a separate
config.

A framework may eventually be good, but the C code also does not use one.
It seems one could wait until there are a few such (micro-)benchmark modules.

Thanks,
Burak