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

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

[Burak Emir]

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.

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 +
 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)
+{
+	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)
+{
+	__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.
+    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.
+            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
+            // Zero-size allocation is ok and yields a dangling pointer.
+            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);
+        }
+        // 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);
+        }
+        // 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 {
+        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 {
+        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 */)
+        }
+    }
+
+    /// 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.
+        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

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

[Tamir Duberstein]

Hi Burak, some comments inline. Hopefully I haven't missed important
context from previous versions.

On Mon, Mar 10, 2025 at 12:21 PM Burak Emir <bqe@google.com> 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.
>
> 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 +
>  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)
> +{
> +       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)
> +{
> +       __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.

Missing article here.

> +///
> +/// # 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.
> +    nbits: usize,

How come this isn't held as u32? There's a lot of conversion to u32
sprinkled around.

> +}
> +
> +impl Drop for Bitmap {
> +    fn drop(&mut self) {
> +        // SAFETY: `self.ptr` was returned by bitmap_zalloc.

Ticks around `bitmap_zalloc` for consistency. I think this should also
have an INVARIANT section since after this call the invariant
described on Bitmap is broken.

> +        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}");
> +}

Have you considered using build_error or returning an error?

> +
> +#[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.
> +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> +            // Zero-size allocation is ok and yields a dangling pointer.
> +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> +            Ok(Bitmap { ptr, nbits })
> +        } else {
> +            Err(AllocError)
> +        }
> +    }

Similar question to above: why return an error here but panic in the setters?

> +
> +    /// 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()
> +    }

Could you describe the need for these functions in the commit message?
I would expect that leaking the internal pointer would be an anti-goal
of an abstraction like this.

> +
> +    /// 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);
> +        }
> +        // 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) {

 nit: `Bitmap` could be `Self` here.

> +        if self.nbits < src.nbits {
> +            panic_not_in_bounds_le("src.nbits", self.nbits, src.nbits);
> +        }
> +        // 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 {
> +        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 {
> +        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 */)
> +        }
> +    }

How come `find_last_bit` exists but `find_next_zero_bit` does not? I
wonder if the APIs could be unified by taking optional sizes and
offsets.

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

Cheers.
Tamir

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

[Miguel Ojeda]

Hi Burak,

Some quick notes...

On Mon, Mar 10, 2025 at 5:20 PM Burak Emir <bqe@google.com> wrote:
>
> +void rust_helper_bitmap_copy_and_extend(unsigned long *dst, const unsigned long *src, unsigned int count, unsigned int size)
> +{
> +       bitmap_copy_and_extend(dst, src, count, size);
> +}

Please use the same parameter names as the real one, i.e. `to` and `from`.

> +/// Wraps underlying C bitmap structure.

I am not sure I would say it "structure" here, i.e. it seems like it
actually wraps a C `struct bitmap`.

In general, we also try to mention the "wraps ..." (if it actually did
so) in a second paragraph, rather than doing so in the title.

> +/// # Invariants
> +///
> +/// * `ptr` is obtained from a successful call to `bitmap_zalloc` and

Also, you may remove the bullet list -- we currently do not enforce
that it is always a bullet list (though we may in the future).

> +    /// Pointer to an array of unsigned long.

`unsigned long`

> +    ptr: NonNull<usize>,
> +    /// How many bits this bitmap stores. Must be < 2^32.

Should the "Must be" be part of the invariants above?

> +        // SAFETY: `self.ptr` was returned by bitmap_zalloc.

"the C `bitmap_zalloc`"

> +impl Bitmap {
> +    /// Constructs a new [`Bitmap`].
> +    ///
> +    /// Fails with AllocError if `nbits` is greater than or equal to 2^32,

Intra-doc links where possible: [`AllocError`].

> +    /// # Example

We use plurals even if there is a single example (like for the invariants).

> +    /// ```
> +    /// # use kernel::bitmap::Bitmap;
> +    ///
> +    /// fn new_bitmap() -> Bitmap {
> +    ///   Bitmap::new(128, GFP_KERNEL).unwrap()
> +    /// }
> +    /// ```

Is there a reason why this example cannot be run? i.e. to not have it
wrapped in a function.

Also, please use the `?` operator if possible -- we try to write
examples as "real code", so we try to avoid `unwrap()` etc.

> +            Ok(Bitmap { ptr, nbits })

When we have invariants, we use an `// INVARIANT: ...` comment (please
grep for similar cases to see how it is usually done).

> +    /// Returns how many bits this bitmap holds.

We should have examples (which double as tests) for these.

One alternative, that may be simpler to showcase how the type works,
is to write a longer example in the documentation of the type itself.

> +        // SAFETY: nbits == 0 is supported and access is within bounds.

Markdown wherever possible, e.g. `nbits == 0` (also other instance).

Thanks!

Cheers,
Miguel

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

[Yury Norov]

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

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

[Yury Norov]

On Mon, Mar 10, 2025 at 05:53:10PM +0100, Miguel Ojeda wrote:
> Hi Burak,
> 
> Some quick notes...
> 
> On Mon, Mar 10, 2025 at 5:20 PM Burak Emir <bqe@google.com> wrote:
> >
> > +void rust_helper_bitmap_copy_and_extend(unsigned long *dst, const unsigned long *src, unsigned int count, unsigned int size)
> > +{
> > +       bitmap_copy_and_extend(dst, src, count, size);
> > +}
> 
> Please use the same parameter names as the real one, i.e. `to` and `from`.
> 
> > +/// Wraps underlying C bitmap structure.
> 
> I am not sure I would say it "structure" here, i.e. it seems like it
> actually wraps a C `struct bitmap`.

There's no such a thing like 'struct bitmap'. It's internally an array
of unsigned longs. I'd rather say it like:

        Wraps underlying C bitmap API.
 

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

[Miguel Ojeda]

On Mon, Mar 10, 2025 at 7:18 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> There's no such a thing like 'struct bitmap'. It's internally an array
> of unsigned longs.

Yeah, that is why I said it, i.e. the docs seemed to imply it was
wrapping a C structure.

(There happens to be a `struct bitmap` in a driver, though! I noticed
because I double-checked with Elixir... :)

Cheers,
Miguel

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

[Burak Emir]

On Mon, Mar 10, 2025 at 5:53 PM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> Hi Burak,
>
> Some quick notes...
>
> On Mon, Mar 10, 2025 at 5:20 PM Burak Emir <bqe@google.com> wrote:
> >
> > +void rust_helper_bitmap_copy_and_extend(unsigned long *dst, const unsigned long *src, unsigned int count, unsigned int size)
> > +{
> > +       bitmap_copy_and_extend(dst, src, count, size);
> > +}
>
> Please use the same parameter names as the real one, i.e. `to` and `from`.
>
> > +/// Wraps underlying C bitmap structure.
>
> I am not sure I would say it "structure" here, i.e. it seems like it
> actually wraps a C `struct bitmap`.
>
> In general, we also try to mention the "wraps ..." (if it actually did
> so) in a second paragraph, rather than doing so in the title.
>
> > +/// # Invariants
> > +///
> > +/// * `ptr` is obtained from a successful call to `bitmap_zalloc` and
>
> Also, you may remove the bullet list -- we currently do not enforce
> that it is always a bullet list (though we may in the future).
>
> > +    /// Pointer to an array of unsigned long.
>
> `unsigned long`
>
> > +    ptr: NonNull<usize>,
> > +    /// How many bits this bitmap stores. Must be < 2^32.
>
> Should the "Must be" be part of the invariants above?
>
> > +        // SAFETY: `self.ptr` was returned by bitmap_zalloc.
>
> "the C `bitmap_zalloc`"
>
> > +impl Bitmap {
> > +    /// Constructs a new [`Bitmap`].
> > +    ///
> > +    /// Fails with AllocError if `nbits` is greater than or equal to 2^32,
>
> Intra-doc links where possible: [`AllocError`].
>
> > +    /// # Example
>
> We use plurals even if there is a single example (like for the invariants).
>
> > +    /// ```
> > +    /// # use kernel::bitmap::Bitmap;
> > +    ///
> > +    /// fn new_bitmap() -> Bitmap {
> > +    ///   Bitmap::new(128, GFP_KERNEL).unwrap()
> > +    /// }
> > +    /// ```
>
> Is there a reason why this example cannot be run? i.e. to not have it
> wrapped in a function.
>
> Also, please use the `?` operator if possible -- we try to write
> examples as "real code", so we try to avoid `unwrap()` etc.
>
> > +            Ok(Bitmap { ptr, nbits })
>
> When we have invariants, we use an `// INVARIANT: ...` comment (please
> grep for similar cases to see how it is usually done).
>
> > +    /// Returns how many bits this bitmap holds.
>
> We should have examples (which double as tests) for these.
>
> One alternative, that may be simpler to showcase how the type works,
> is to write a longer example in the documentation of the type itself.
>
> > +        // SAFETY: nbits == 0 is supported and access is within bounds.
>
> Markdown wherever possible, e.g. `nbits == 0` (also other instance).
>
> Thanks!
>

Thanks, all done. Paying more attention to the markdown now and adding
a longer example.

Cheers,
Burak

> Cheers,
> Miguel

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

[Burak Emir]

On Mon, Mar 10, 2025 at 7:12 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> 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?

Will do, after checking with Alice.
Agree it should be much easier to review.

> > 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.
>
Will do.

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

Fixed. I had edited after running 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.
>

Fixed.

> > +{
> > +     __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
>
Thanks for the catch, using the Rust constant u32::MAX.

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

As we only need to check bounds here once, we can use `usize`
as is the choice for all indices in Rust.
As above, changed to u32::MAX.

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

I copied from dbitmap, but more importantly Rust requires that when
memory is accessed, it has to be initialized before. So if I used alloc,
I'd have to initialize manually.

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

Changing to "Bit number".

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

Yeah, I realize this is a bit hard to read. Made the check consistent
with the panic message call.

> 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().
>

A general bound checking macro BUG_ON sounds interesting
I will have to ask the other folks about this. For now, I'd like
to keep the simpler but more verbose if & panic.

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

Tamir asked about these as well. I think I misunderstood the
C API as supporting partial search, and wanted to make
sure the functionality is preserved.

I now realize that the intention of the size parameter is to always
pass the size. Will remove.

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

No, I just looked at the find_first_zero implementation and thought
that it supports partial search. Removing.

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

Good point, I will remove this and expose only the variant with offset.
That is the one used by dbitmap anyways.

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

I assume you are asking about the SAFETY comment, not the bound check.

The convention with SAFETY comments is in the Rust coding guidelines.
The comments are there to convince the reader that the
immediately-following "unsafe {...}" block can never lead to undefined behavior.
I looked at the C code and documented that it is safe, so the reader
does not have to. The goal
is to enable local reasoning, so the reader can check a piece of code
in isolation.

I call out the nbits == 0 case every time, because we are passing a
dangling pointer to C.
It may not be very obvious that this is an ok thing to do, and
explicit is better than implicit.

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

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

[Burak Emir]

(adding everyone back to cc, sorry.)

On Mon, Mar 10, 2025 at 10:05 PM Burak Emir <bqe@google.com> wrote:
>
> On Mon, Mar 10, 2025 at 9:42 PM Tamir Duberstein <tamird@gmail.com> wrote:
> >
> > On Mon, Mar 10, 2025 at 4:27 PM Burak Emir <bqe@google.com> wrote:
> > >
> > > On Mon, Mar 10, 2025 at 5:45 PM Tamir Duberstein <tamird@gmail.com> wrote:
> > > >
> > > > Hi Burak, some comments inline. Hopefully I haven't missed important
> > > > context from previous versions.
> > >
> > > Thanks for taking a look!
> > >
>
> Somehow I managed to hit Reply instead of Reply-All.
> I now wonder what happens with the threading if I add everyone back to cc :/
>
> > > > On Mon, Mar 10, 2025 at 12:21 PM Burak Emir <bqe@google.com> 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.
> > > > >
> > > > > 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 +
> > > > >  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)
> > > > > +{
> > > > > +       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)
> > > > > +{
> > > > > +       __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.
> > > >
> > > > Missing article here.
> > > >
> > > Ack, will reword.
> > >
> > > > > +///
> > > > > +/// # 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.
> > > > > +    nbits: usize,
> > > >
> > > > How come this isn't held as u32? There's a lot of conversion to u32
> > > > sprinkled around.
> > > >
> > > On the C side, there is a limitation to a maximum of 2^32 bits. This is
> > > unfortunately not consistently used as argument type. Therefore one
> > > needs to cast in a few places. So if we used u32, we'd have to cast to usize.
> > >
> > > Since usize is the idiomatic Rust choice for all sorts of indices, we use usize.
> >
> > On the other hand u32 to usize cannot go out of bounds, while the
> > inverse isn't true.
> >
> > >
> > > > > +}
> > > > > +
> > > > > +impl Drop for Bitmap {
> > > > > +    fn drop(&mut self) {
> > > > > +        // SAFETY: `self.ptr` was returned by bitmap_zalloc.
> > > >
> > > > Ticks around `bitmap_zalloc` for consistency. I think this should also
> > > > have an INVARIANT section since after this call the invariant
> > > > described on Bitmap is broken.
> > >
> > > Fixed the comment.
> > >
> > > I think I'd agree if there was anything happening after the call.
> > > As it stands, drop() is finished after the call, the value will be gone,
> > > and the stated invariant does not apply anymore.
> > >
> > > Are you worried about future additions to the struct?
> > > I could not find any example of a Drop impl where people bothered
> > >  to talk about invariants.
> >
> > Please see https://lore.kernel.org/all/20250221-rust-xarray-bindings-v18-2-cbabe5ddfc32@gmail.com/.
> >
>
> Thanks, I added a similar text now.
>
> > >
> > > > > +        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}");
> > > > > +}
> > > >
> > > > Have you considered using build_error or returning an error?
> > > >
> > >
> > > The bounds checks are done at runtime. There is client
> > > code that constructs bitmaps with an argument that is
> > > only known at runtime.
> >
> > Why not return an error?
> >
>
> A programmer mistake that messes up the bounds is not a recoverable
> situation, but a bug.
>
> > >
> > > > > +
> > > > > +#[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.
> > > > > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > > > > +            // Zero-size allocation is ok and yields a dangling pointer.
> > > > > +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> > > > > +            Ok(Bitmap { ptr, nbits })
> > > > > +        } else {
> > > > > +            Err(AllocError)
> > > > > +        }
> > > > > +    }
> > > >
> > > > Similar question to above: why return an error here but panic in the setters?
> > >
> > > The reasoning here is that:
> > > - failing bounds check is considered a programming error. Panic is
> > > better than undefined behavior.
> > > - however, memory allocation can fail also when the code is correct.
> >
> > `new` returns an error when the requested size is out of bounds; isn't
> > that a programming error? This doesn't appear to be consistent.
>
> I agree with this. Changing to panicking if nbits is too large.
>
> > >
> > > > > +
> > > > > +    /// 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()
> > > > > +    }
> > > >
> > > > Could you describe the need for these functions in the commit message?
> > > > I would expect that leaking the internal pointer would be an anti-goal
> > > > of an abstraction like this.
> > > >
> > >
> > > Having access to pointers is not a problem, it is
> > > dereferencing of pointers that means leaving behind the
> > > guarantees of static checking and thus requires `unsafe`.
> >
> > I didn't say anything about safety. It is just plain old abstraction breaking.
> >
>
> I see what you mean. Made these private.
>
> > >
> > > As there may be situations where client code may have to
> > > call underlying C methods with this pointers (which will also
> > > requires `unsafe` and safety comments) it should be ok to
> > > enable that.
> >
> > Should it? It would seem to me that such a situation is indicative of
> > an incomplete abstraction.
> >
>
> Agree it would certainly be desirable to hide the pointer. I realize I do
> not have an actual case where the pointer is needed outside
> the trait impl, and when the dbitmap is rewritten in Rust it
> should not have to deal with the pointer. So these are private now.
>
> > >
> > > > > +
> > > > > +    /// 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);
> > > > > +        }
> > > > > +        // 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) {
> > > >
> > > >  nit: `Bitmap` could be `Self` here.
> > > >
> > > Done.
> > >
> > > > > +        if self.nbits < src.nbits {
> > > > > +            panic_not_in_bounds_le("src.nbits", self.nbits, src.nbits);
> > > > > +        }
> > > > > +        // 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 {
> > > > > +        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 {
> > > > > +        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 */)
> > > > > +        }
> > > > > +    }
> > > >
> > > > How come `find_last_bit` exists but `find_next_zero_bit` does not? I
> > > > wonder if the APIs could be unified by taking optional sizes and
> > > > offsets.
> > > >
> > >
> > > Yeah, it would be good if a convention would emerge that one could
> > > then follow. This patch bundles pointer and nbits into a struct, so clients
> > > of the Rust API will not have to provide size.
> > >
> > > On the other hand, the C API takes an argument and it could be anything,
> > > also a number below size.
> > >
> > > I found it clearest to preserve the full flexibility of the API while giving
> > > convenient alternative for the common case.
> >
> > I don't think this answers my questions.
> >
>
> I also got comments from Yury about these, so will have to think about this.
>
> When I add the dbitmap use case, at least it will be clearer what is used.
>
> There is a general issue that C APIs take a size parameter. Maybe the
> intention is to always pass the size, but the implementation also
> supports passing in some number that is smaller than the bitmaps size.
>
> As a reader of the C API, I thought this functionality might be needed.
> If it is not needed, then there is also no need to offer a size parameter
> in the Rust API (since we already have the size).
>
> offset could be an option parameter. As I said, let me see what other
> comments I have, and add the dbitmap client code. Hopefully that
> makes things a bit clearer.
>
> > >
> > > > > +
> > > > > +    /// 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.
> > > > > +        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
> > > > >
> > > > >
> > >
> > > Thanks,
> > > Burak

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

[Yury Norov]

On Mon, Mar 10, 2025 at 11:01:37PM +0100, Burak Emir wrote:
> > > +            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?
> >
> 
> I copied from dbitmap, but more importantly Rust requires that when
> memory is accessed, it has to be initialized before. So if I used alloc,
> I'd have to initialize manually.

If you have a pointer to a memory area of size 0, it's unsafe to
even dereference it. Luckily, initialization of 0-bit array is a
no-op. I don't understand how to initialize 0 bits.

This dbitmap thing looks messy. It uses atomic set_bit() where
non-atomic should be used. Now it encourages to create 0-sized
bitmaps. Please don't copy anything blindly from there...

[...]

> On Mon, Mar 10, 2025 at 7:12 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > +    /// 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?
> >
> 
> Yeah, I realize this is a bit hard to read. Made the check consistent
> with the panic message call.
> 
> > 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().
> 
> A general bound checking macro BUG_ON sounds interesting
> I will have to ask the other folks about this. For now, I'd like
> to keep the simpler but more verbose if & panic.

I don't suggest to use BUG_ON(). I suggest to use similar semantics.
You repeat that 3 lines again and again. It cries to become a nice
macro.
 
> > > +        }
> > > +        // 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.
> >
> 
> Tamir asked about these as well. I think I misunderstood the
> C API as supporting partial search, and wanted to make
> sure the functionality is preserved.
> 
> I now realize that the intention of the size parameter is to always
> pass the size. Will remove.

OK, good. You may look at cpumasks and nodemasks - those are 2 most
developed wrappers around bitmaps, and good examples of the API usage.

> > > +        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?
> >
> 
> No, I just looked at the find_first_zero implementation and thought
> that it supports partial search. Removing.

In C user provides nbits explicitly, so partial search is allowed
automatically. Here you pack a pointer with size, and it makes your
API less robust. This robustness may or may not be needed by users.
Cpumasks and nodemasks don't need floating nbits, so they just hardcode
it.

You didn't show the actual code, and I don't understand what exactly do
you need. If you want to operate on first nbits, just don't attach size
to the pointer, IMO...

> > > +        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.
> >
> 
> Good point, I will remove this and expose only the variant with offset.
> That is the one used by dbitmap anyways.
> 
> > > +        }
> > > +    }
> > > +
> > > +    /// 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.
> >
> 
> I assume you are asking about the SAFETY comment, not the bound check.

No, I'm asking about your panic()s. find_bit() functions don't dereference
memory that is out of boundaries, and don't crash the kernel. If nbits is
0, or offset >= nbits, find_bit() returns immediately and doesn't touch
any memory. But you may want to print a message and go panic. This is not
how the original find_bit() works. But you may want to do it for debugging
or hardening reasons.

So I wanted to clarify: is it intentional? Maybe add a comment? Also,
if it's a debugging feature, you most likely need to make it depending
on CONFIG_DEBUG_XXX.

Thanks,
Yury

> The convention with SAFETY comments is in the Rust coding guidelines.
> The comments are there to convince the reader that the
> immediately-following "unsafe {...}" block can never lead to undefined behavior.
> I looked at the C code and documented that it is safe, so the reader
> does not have to. The goal
> is to enable local reasoning, so the reader can check a piece of code
> in isolation.
>
> I call out the nbits == 0 case every time, because we are passing a
> dangling pointer to C.
> It may not be very obvious that this is an ok thing to do, and
> explicit is better than implicit.
> 
> > > +        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

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

[Alice Ryhl]

On Mon, Mar 10, 2025 at 02:12:22PM -0400, Yury Norov wrote:
> 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?

Rust Binder is not upstream yet. We are upstreaming its dependencies
before the driver itself, so there will be dead code no matter what. The
number of dependencies is so large that it's completely impractical to
land them together with the driver.

We can include a patch that includes the wrapper data structure that
Rust Binder builds on top of bitmap. We can also include a link to the
Rust Binder change that makes Binder start using this code.

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

I do think that it makes sense to allow a bitmap of size zero. We allow
bitmaps of any other length. Why should that length be special?

Of course, I guess it might make sense to not call `bitmap_zalloc` when
calling `new(0)`? But kmalloc does seem to allow them.

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

We could use
assert!(src.nbits <= self.nbits, "Copy: out of bounds.");

but using these explicit function calls would generate less code and
avoid duplicating the error messages.

Also, we should add #[track_caller] to these methods so that the line
number in the panic message is taken from the caller rather than this
file.

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

Ah, that's nice! I do think it's still good to have them for hardening
reasons. Passing an out-of-bouds offset is a bug.

Alice

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

[Alice Ryhl]

On Mon, Mar 10, 2025 at 12:44:59PM -0400, Tamir Duberstein wrote:
> Hi Burak, some comments inline. Hopefully I haven't missed important
> context from previous versions.
> 
> On Mon, Mar 10, 2025 at 12:21 PM Burak Emir <bqe@google.com> wrote:
> > +/// # 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.
> > +    nbits: usize,
> 
> How come this isn't held as u32? There's a lot of conversion to u32
> sprinkled around.

Then we would need conversions to usize in other places. I think the
right choice of type in the public API here is usize, but the underlying
C API uses int in various places.

> > +#[cold]
> > +fn panic_not_in_bounds_lt(arg: &'static str, len: usize, val: usize) -> ! {
> > +    panic!("{arg} must be less than length {len}, was {val}");
> > +}
> 
> Have you considered using build_error or returning an error?

I think using build error for these is a bad idea. It's a hack that Rust
doesn't support well, and the optimizer will not always be able to prove
that the integer is in bounds.

> > +    /// 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.
> > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > +            // Zero-size allocation is ok and yields a dangling pointer.
> > +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> > +            Ok(Bitmap { ptr, nbits })
> > +        } else {
> > +            Err(AllocError)
> > +        }
> > +    }
> 
> Similar question to above: why return an error here but panic in the setters?

Out of memory is something the caller must handle. There's no way for
the caller to avoid it.

Out of bounds is a bug in the caller. The caller can avoid it by not
passing too large indices.

Alice

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

[Yury Norov]

On Tue, Mar 11, 2025 at 10:07:15AM +0000, Alice Ryhl wrote:
> On Mon, Mar 10, 2025 at 02:12:22PM -0400, Yury Norov wrote:
> > 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?
> 
> Rust Binder is not upstream yet. We are upstreaming its dependencies
> before the driver itself, so there will be dead code no matter what. The
> number of dependencies is so large that it's completely impractical to
> land them together with the driver.

I don't ask to upstream all at once. But at least dbitmaps is less
than 200 LOCs in C. Together with a test that demonstrates how you're
using it, it would be enough.
 
> We can include a patch that includes the wrapper data structure that
> Rust Binder builds on top of bitmap. We can also include a link to the
> Rust Binder change that makes Binder start using this code.
>
> > > +            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?
> 
> I do think that it makes sense to allow a bitmap of size zero. We allow
> bitmaps of any other length. Why should that length be special?
> 
> Of course, I guess it might make sense to not call `bitmap_zalloc` when
> calling `new(0)`? But kmalloc does seem to allow them.

Without looking at the code it's "I think vs you think". 

> > > +    /// 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().
> 
> We could use
> assert!(src.nbits <= self.nbits, "Copy: out of bounds.");
> 
> but using these explicit function calls would generate less code and
> avoid duplicating the error messages.

What I see is that you generate more code - 3 lines vs 1.

Do you have any numbers supporting your statement? Can you show how
exactly the messages are duplicated when using assert()? Can this
assert() be fixed to avoid duplication?

> Also, we should add #[track_caller] to these methods so that the line
> number in the panic message is taken from the caller rather than this
> file.
> 
> > > +        }
> > > +    }
> > > +
> > > +    /// 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.
> 
> Ah, that's nice! I do think it's still good to have them for hardening
> reasons. Passing an out-of-bouds offset is a bug.

Ironically, you don't test the offset for safety.

Whether it's a bug or not - depends on algorithm you're implementing. 
Check how for_each_set_bitrange() works. For it, offset >= nbits is
expected, at last iteration. It's completely safe, although out-of-range.

Thanks,
Yury

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

[Alice Ryhl]

On Tue, Mar 11, 2025 at 10:33:10AM -0400, Yury Norov wrote:
> On Tue, Mar 11, 2025 at 10:07:15AM +0000, Alice Ryhl wrote:
> > On Mon, Mar 10, 2025 at 02:12:22PM -0400, Yury Norov wrote:
> > > 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?
> > 
> > Rust Binder is not upstream yet. We are upstreaming its dependencies
> > before the driver itself, so there will be dead code no matter what. The
> > number of dependencies is so large that it's completely impractical to
> > land them together with the driver.
> 
> I don't ask to upstream all at once. But at least dbitmaps is less
> than 200 LOCs in C. Together with a test that demonstrates how you're
> using it, it would be enough.

Sounds good.

> > We can include a patch that includes the wrapper data structure that
> > Rust Binder builds on top of bitmap. We can also include a link to the
> > Rust Binder change that makes Binder start using this code.
> >
> > > > +            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?
> > 
> > I do think that it makes sense to allow a bitmap of size zero. We allow
> > bitmaps of any other length. Why should that length be special?
> > 
> > Of course, I guess it might make sense to not call `bitmap_zalloc` when
> > calling `new(0)`? But kmalloc does seem to allow them.
> 
> Without looking at the code it's "I think vs you think". 

The include/linux/slab.h file says:

/*
 * ZERO_SIZE_PTR will be returned for zero sized kmalloc requests.
 *
 * Dereferencing ZERO_SIZE_PTR will lead to a distinct access fault.
 *
 * ZERO_SIZE_PTR can be passed to kfree though in the same way that NULL can.
 * Both make kfree a no-op.
 */
#define ZERO_SIZE_PTR ((void *)16)

> > > > +    /// 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().
> > 
> > We could use
> > assert!(src.nbits <= self.nbits, "Copy: out of bounds.");
> > 
> > but using these explicit function calls would generate less code and
> > avoid duplicating the error messages.
> 
> What I see is that you generate more code - 3 lines vs 1.
> 
> Do you have any numbers supporting your statement? Can you show how
> exactly the messages are duplicated when using assert()? Can this
> assert() be fixed to avoid duplication?

The statement comes from having multiple string literals containing
similar strings. They might get deduplicated if they're completely
equal, I guess. Having many methods call one shared function ensures
that the binary will only have one copy of the string literal.

> > > > +        }
> > > > +    }
> > > > +
> > > > +    /// 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.
> > 
> > Ah, that's nice! I do think it's still good to have them for hardening
> > reasons. Passing an out-of-bouds offset is a bug.
> 
> Ironically, you don't test the offset for safety.
> 
> Whether it's a bug or not - depends on algorithm you're implementing. 
> Check how for_each_set_bitrange() works. For it, offset >= nbits is
> expected, at last iteration. It's completely safe, although out-of-range.
> 
> Thanks,
> Yury