Re: [PATCH v3] rust: add bindings and API for bitmap.h and bitops.h.

[Yury Norov <yury.norov@gmail.com>]

On Mon, Mar 10, 2025 at 04:19:46PM +0000, Burak Emir wrote:
> Adds a Rust bitmap API and necessary bitmap and bitops bindings.
> These are 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.

Please add it in the same series that converts dbitmap to rust. This
all is a dead code otherwise, right?

> The Rust bitmap API provides an abstraction to underlying bitmap
> and bitops operations. For now, we only include methods that are
> necessary for reimplementing dbitmap.h. It is straightforward to add
> more methods later, as needed. We offer a safe API through
> bounds checks which panic if violated.
> 
> We introduce bindings for the non-atomic variants __set_bit and
> __clear_bit, and use the _find_* variants instead of the find_*
> wrappers which enable small size optimization in C. These C
> small size optimizations do not carry over to Rust. The
> principle followed is that whenever there are plain variants, we use
> those.
> 
> This series uses 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.
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
> This is v3 of a patch introducing Rust bitmap API [v2]. Thanks
> for all the helpful comments!
> 
> 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 patch [1] and Viresh's v2 patch [2]
> - 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/all/cover.1740726226.git.viresh.kumar@linaro.org/
> Link [v2]: https://lore.kernel.org/rust-for-linux/20250303114037.3259804-2-bqe@google.com/
> ---
>  MAINTAINERS                     |   8 ++
>  rust/bindings/bindings_helper.h |   1 +
>  rust/helpers/bitmap.c           |   8 ++
>  rust/helpers/bitops.c           |  13 +++
>  rust/helpers/helpers.c          |   2 +
>  rust/kernel/bitmap.rs           | 190 ++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs              |   1 +

Please submit rust code in a separate patch.

>  7 files changed, 223 insertions(+)
>  create mode 100644 rust/helpers/bitmap.c
>  create mode 100644 rust/helpers/bitops.c
>  create mode 100644 rust/kernel/bitmap.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 6d6e55d8593b..8f42fb1f24c6 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4032,12 +4032,15 @@ 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
>  
>  BITMAP API [RUST]
>  M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
> +M:	Alice Ryhl <aliceryhl@google.com> (bitmap)
>  R:	Yury Norov <yury.norov@gmail.com>
>  S:	Maintained
> +F:	rust/kernel/bitmap.rs
>  F:	rust/kernel/cpumask.rs
>  
>  BITOPS API
> @@ -4054,6 +4057,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/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
> index 673b1daa9a58..50416c1a3de9 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..1cc88b34d716
> --- /dev/null
> +++ b/rust/helpers/bitmap.c
> @@ -0,0 +1,8 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bitmap.h>
> +
> +void rust_helper_bitmap_copy_and_extend(unsigned long *dst, const unsigned long *src, unsigned int count, unsigned int size)

How long is this line? Did you run checkpatch?

> +{
> +	bitmap_copy_and_extend(dst, src, count, size);
> +}
> diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c
> new file mode 100644
> index 000000000000..986dafb45184
> --- /dev/null
> +++ b/rust/helpers/bitops.c
> @@ -0,0 +1,13 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bitops.h>
> +
> +void rust_helper___set_bit(unsigned int nr, volatile unsigned long *addr)
> +{
> +	__set_bit(nr, addr);
> +}
> +
> +void rust_helper___clear_bit(unsigned int nr, volatile unsigned long *addr)

Volatile is only for atomic ops.

> +{
> +	__clear_bit(nr, addr);
> +}
> diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
> index de2341cfd917..541d8cb30195 100644
> --- a/rust/helpers/helpers.c
> +++ b/rust/helpers/helpers.c
> @@ -7,6 +7,8 @@
>   * Sorted alphabetically.
>   */
>  
> +#include "bitmap.c"
> +#include "bitops.c"
>  #include "blk.c"
>  #include "bug.c"
>  #include "build_assert.c"
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> new file mode 100644
> index 000000000000..b8fe18dff832
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,190 @@
> +// 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;
> +
> +/// Wraps underlying C bitmap structure.
> +///
> +/// # Invariants
> +///
> +/// * `ptr` is 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 {
> +    /// Pointer to an array of unsigned long.
> +    ptr: NonNull<usize>,
> +    /// How many bits this bitmap stores. Must be < 2^32.

Must be < INT_MAX, i.e. 2^32 - 1

> +    nbits: usize,
> +}
> +
> +impl Drop for Bitmap {
> +    fn drop(&mut self) {
> +        // SAFETY: `self.ptr` was returned by bitmap_zalloc.
> +        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
> +    }
> +}
> +
> +#[cold]
> +fn panic_not_in_bounds_lt(arg: &'static str, len: usize, val: usize) -> ! {
> +    panic!("{arg} must be less than length {len}, was {val}");
> +}
> +
> +#[cold]
> +fn panic_not_in_bounds_le(arg: &'static str, len: usize, val: usize) -> ! {
> +    panic!("{arg} must be less than or equal to length {len}, was {val}");
> +}
> +
> +impl Bitmap {
> +    /// Constructs a new [`Bitmap`].
> +    ///
> +    /// Fails with AllocError if `nbits` is greater than or equal to 2^32,
> +    /// or when the bitmap could not be allocated.
> +    ///
> +    /// # Example
> +    ///
> +    /// ```
> +    /// # use kernel::bitmap::Bitmap;
> +    ///
> +    /// fn new_bitmap() -> Bitmap {
> +    ///   Bitmap::new(128, GFP_KERNEL).unwrap()
> +    /// }
> +    /// ```
> +    #[inline]
> +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> +        if let Ok(nbits_u32) = u32::try_from(nbits) {
> +            // SAFETY: nbits == 0 is permitted and nbits fits in u32.

Different parts of bitmaps API have different types for the 'nbits'
The safe way would be limit it to 32-bit signed INT_MAX.

(This is a historical mess.)

> +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> +            // Zero-size allocation is ok and yields a dangling pointer.

Zero-sized allocation makes no sense, and usually is a sign of a bug.
What for you explicitly allow it?

> +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> +            Ok(Bitmap { ptr, nbits })
> +        } else {
> +            Err(AllocError)
> +        }
> +    }
> +
> +    /// Returns how many bits this bitmap holds.
> +    #[inline]
> +    pub fn len(&self) -> usize {
> +        self.nbits
> +    }
> +
> +    /// Returns true if this bitmap has length 0.
> +    #[inline]
> +    pub fn is_empty(&self) -> bool {
> +        self.nbits == 0
> +    }
> +
> +    /// Returns a mutable raw pointer to the backing bitmap.
> +    #[inline]
> +    pub fn as_mut_ptr(&mut self) -> *mut usize {
> +        self.ptr.as_ptr()
> +    }
> +
> +    /// Returns a raw pointer to the backing bitmap.
> +    #[inline]
> +    pub fn as_ptr(&self) -> *const usize {
> +        self.ptr.as_ptr()
> +    }
> +
> +    /// Sets bit with number `nr`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `nr` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn set_bit(&mut self, nr: usize) {
> +        if self.nbits <= nr {
> +            panic_not_in_bounds_lt("nr", self.nbits, nr)
> +        }
> +        // SAFETY: Bit nr is within bounds.
> +        unsafe { bindings::__set_bit(nr as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Clears bit with number `nr`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `nr` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn clear_bit(&mut self, nr: usize) {
> +        if self.nbits <= nr {
> +            panic_not_in_bounds_lt("nr", self.nbits, nr);

"nr" what? If you add a message, I believe it should be a somewhat
informative message.

> +        }
> +        // SAFETY: Bit nr is within bounds.
> +        unsafe { bindings::__clear_bit(nr as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Copies all bits from `src` and sets any remaining bits to zero.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `src.nbits` has more bits than this bitmap.
> +    #[inline]
> +    pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) {
> +        if self.nbits < src.nbits {
> +            panic_not_in_bounds_le("src.nbits", self.nbits, src.nbits);

The _lt usually stands for 'less than', or '<'. And _le is 'less than or
equal', or '<='. But in your code you do exactly opposite. Is that on
purpose?

Also, you can make it similar to BUG_ON() semantics, so that it will
be a single line of code, not 3:

        RUST_PANIC("Copy: out of bonds", self.nbits < src.nbits);

And to that extend, panic message should be available to all rust
subsystems, just like BUG_ON().

> +        }
> +        // SAFETY: nbits == 0 is supported and access to `self` and `src` is within bounds.
> +        unsafe {
> +            bindings::bitmap_copy_and_extend(self.as_mut_ptr(), src.as_ptr(), src.nbits as u32, self.nbits as u32)
> +        };
> +    }
> +
> +    /// Finds the last bit.
> +    #[inline]
> +    pub fn find_last_bit(&self) -> usize {
> +        // SAFETY: nbits == 0 is supported and access is within bounds.
> +        unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) }
> +    }
> +
> +    /// Finds the last bit, searching up to `nbits` bits.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `nbits` is too large for this bitmap.
> +    #[inline]
> +    pub fn find_last_bit_upto(&self, nbits: usize) -> usize {

So this is not a binding, right? This is a new function. In C code we
don't support partial search. Can you confirm you need a partial
search here? What's your use scenario?

Really, this should go with the series that converts dbitmap.
Otherwise it's hard to understand what you're trying to do.

> +        if self.nbits < nbits {
> +            panic_not_in_bounds_le("nbits", self.nbits, nbits);
> +        }
> +        // SAFETY: nbits == 0 is supported and access is within bounds.
> +        unsafe { bindings::_find_last_bit(self.as_ptr(), nbits) }
> +    }
> +
> +    /// Finds the next zero bit, searching up to `nbits`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `nbits` is too large for this bitmap.
> +    #[inline]
> +    pub fn find_next_zero_bit_upto(&self, nbits: usize) -> usize {

1. This should be 'find_first_zero_bit'.

2. The same question as to previous function. In this case you will
most likely be OK with plain find_first_zero_bit(). So if it returns a
number greater than 'nbits', it means that first nbits are empty for
sure. Is it a performance trick?

> +        if self.nbits < nbits {
> +            panic_not_in_bounds_le("nbits", self.nbits, nbits);
> +        }
> +        // SAFETY: nbits == 0 is supported and access is within bounds.
> +        unsafe {
> +            bindings::_find_next_zero_bit(self.as_ptr(), nbits, 0 /* offset */)

For offset == 0 we have find_first_bit() functions.

> +        }
> +    }
> +
> +    /// Finds the next zero bit, searching up to `nbits` bits, with offset `offset`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `nbits` is too large for this bitmap.
> +    #[inline]
> +    pub fn find_next_zero_bit_upto_offset(&self, nbits: usize, offset: usize) -> usize {
> +        if self.nbits < nbits {
> +            panic_not_in_bounds_le("nbits", self.nbits, nbits);
> +        }
> +        // SAFETY: nbits == 0 and out-of-bounds offset is supported, and access is within bounds.

find_bit() functions are all safe against nbits == 0 or
offset >= nbits. If you add those panics for hardening reasons - it's
OK. If you add them to make your code safer - you don't need them. The
C version is already safe.

> +        unsafe { bindings::_find_next_zero_bit(self.as_ptr(), nbits, offset) }
> +    }
> +}
> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index efbd7be98dab..be06ffc47473 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.rc0.332.g42c0ae87b1-goog