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

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

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

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

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

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

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

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.