[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@xxxxxxxxxx>
Signed-off-by: Burak Emir <bqe@xxxxxxxxxx>
---
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@xxxxxxxxx/
Link [2] https://lore.kernel.org/all/cover.1740726226.git.viresh.kumar@xxxxxxxxxx/
Link [v2]: https://lore.kernel.org/rust-for-linux/20250303114037.3259804-2-bqe@xxxxxxxxxx/
---
 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@xxxxxxxxx>
 S:	Maintained
+F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
 BITMAP API [RUST]
 M:	Viresh Kumar <viresh.kumar@xxxxxxxxxx> (cpumask)
+M:	Alice Ryhl <aliceryhl@xxxxxxxxxx> (bitmap)
 R:	Yury Norov <yury.norov@xxxxxxxxx>
 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@xxxxxxxxx>
+S:	Maintained
+F:	rust/helpers/bitops.c
+
 BLINKM RGB LED DRIVER
 M:	Jan-Simon Moeller <jansimon.moeller@xxxxxx>
 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