[PATCH v4 0/3] Rust: Add Rust bitmap API, ID pool and bindings.

[PATCH v4 0/3] Rust: Add Rust bitmap API, ID pool and bindings.

[Burak Emir]

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

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

Introduces bindings for the non-atomic variants __set_bit and
__clear_bit, and uses 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.

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.

As requested, also adding the Rust equivalent of dbitmap.h now,
under the dynamic_id_pool.rs. Includes an example of usage
that requires releasing a spinlock, as expected in Binder driver.

This is v4 of a patch introducing Rust bitmap API [v3]. Thanks
for all the helpful comments!

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

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

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

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



Burak Emir (3):
  Adds bitmap.c and bitops.c Rust bindings.
  Adds Rust Bitmap API.
  Add DynamicIdPool Rust API.

 MAINTAINERS                     |  14 ++
 rust/bindings/bindings_helper.h |   1 +
 rust/helpers/bitmap.c           |   9 ++
 rust/helpers/bitops.c           |  13 ++
 rust/helpers/helpers.c          |   2 +
 rust/kernel/bitmap.rs           | 234 ++++++++++++++++++++++++++++++++
 rust/kernel/dynamic_id_pool.rs  | 191 ++++++++++++++++++++++++++
 rust/kernel/lib.rs              |   2 +
 8 files changed, 466 insertions(+)
 create mode 100644 rust/helpers/bitmap.c
 create mode 100644 rust/helpers/bitops.c
 create mode 100644 rust/kernel/bitmap.rs
 create mode 100644 rust/kernel/dynamic_id_pool.rs

-- 
2.49.0.rc1.451.g8f38331e32-goog

[PATCH v4 1/3] Adds bitmap.c and bitops.c Rust bindings.

[Burak Emir]

Adds helpers for bitmap.c and bitops.c to get Rust bindings
for inline methods __set_bit and __clear_bit (these are
non-atomic variants) as well as bitmap_copy_and_extend.

These are needed for providing a basic Rust Bitmap API.
Update MAINTAINERS.

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

diff --git a/MAINTAINERS b/MAINTAINERS
index c43d66bd85f3..50f44d7e5c6e 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4029,6 +4029,12 @@ F:	tools/include/vdso/bits.h
 F:	tools/lib/bitmap.c
 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)
 R:	Yury Norov <yury.norov@gmail.com>
@@ -4049,6 +4055,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 55354e4dec14..6bd4396b9cd3 100644
--- a/rust/bindings/bindings_helper.h
+++ b/rust/bindings/bindings_helper.h
@@ -7,6 +7,7 @@
  */
 
 #include <kunit/test.h>
+#include <linux/bitmap.h>
 #include <linux/blk-mq.h>
 #include <linux/blk_types.h>
 #include <linux/blkdev.h>
diff --git a/rust/helpers/bitmap.c b/rust/helpers/bitmap.c
new file mode 100644
index 000000000000..a50e2f082e47
--- /dev/null
+++ b/rust/helpers/bitmap.c
@@ -0,0 +1,9 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bitmap.h>
+
+void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long *from,
+		unsigned int count, unsigned int size)
+{
+	bitmap_copy_and_extend(to, from, count, size);
+}
diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c
new file mode 100644
index 000000000000..0ea1611b95dc
--- /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, unsigned long *addr)
+{
+	__set_bit(nr, addr);
+}
+
+void rust_helper___clear_bit(unsigned int nr, unsigned long *addr)
+{
+	__clear_bit(nr, addr);
+}
diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
index 0640b7e115be..74e5e10694a4 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"
-- 
2.49.0.rc1.451.g8f38331e32-goog

[PATCH v4 2/3] Adds Rust Bitmap API.

[Burak Emir]

Provides an abstraction for C bitmap API and bitops operations.
This includes enough functionality to reimplementing a Binder
data structure (drivers/android/dbitmap.h). More methods can be
added later. We offer a safe API through bounds checks which
panic if violated.

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

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

diff --git a/MAINTAINERS b/MAINTAINERS
index 50f44d7e5c6e..b3bbce9274f0 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4036,9 +4036,11 @@ F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
 BITMAP API [RUST]
+M:	Alice Ryhl <aliceryhl@google.com> (bitmap)
 M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
 R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
+F:	rust/kernel/bitmap.rs
 F:	rust/kernel/cpumask.rs
 
 BITOPS API
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
new file mode 100644
index 000000000000..e8117e0dbe05
--- /dev/null
+++ b/rust/kernel/bitmap.rs
@@ -0,0 +1,234 @@
+// 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;
+
+/// Represents a bitmap.
+///
+/// Wraps underlying C bitmap API.
+///
+/// # Examples
+///
+/// Basic usage
+/// ```
+/// use kernel::alloc::flags::GFP_KERNEL;
+/// use kernel::bitmap::Bitmap;
+///
+/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
+/// assert_eq!(16, b.len());
+/// for i in 0..16 {
+///   if i % 4 == 0 {
+///     b.set_bit(i);
+///   }
+/// }
+/// assert_eq!(Some(1), b.find_next_zero_bit(0));
+/// assert_eq!(Some(5), b.find_next_zero_bit(5));
+/// assert_eq!(Some(12), b.find_last_bit());
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// # 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.
+/// `nbits` is `<= u32::MAX` and never changes.
+pub struct Bitmap {
+    /// Pointer to an array of `unsigned long`.
+    ptr: NonNull<usize>,
+    /// How many bits this bitmap stores. Must be `<= u32::MAX`.
+    nbits: usize,
+}
+
+impl Drop for Bitmap {
+    fn drop(&mut self) {
+        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
+        //
+        // INVARIANT: there is no other use of the `self.ptr` after this
+        // call and the value is being dropped so the broken invariant is
+        // not observable on function exit.
+        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
+    }
+}
+
+impl Bitmap {
+    /// Constructs a new [`Bitmap`].
+    ///
+    /// Fails with [`AllocError`] when the [`Bitmap`] could not be
+    /// allocated. This includes the case when `nbits` is greater
+    /// than `u32::MAX`.
+    #[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 <= u32::MAX`.
+            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)?;
+            // INVARIANT: ptr returned by C `bitmap_zalloc` and nbits checked.
+            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]
+    fn as_mut_ptr(&mut self) -> *mut usize {
+        self.ptr.as_ptr()
+    }
+
+    /// Returns a raw pointer to the backing [`Bitmap`].
+    #[inline]
+    fn as_ptr(&self) -> *const usize {
+        self.ptr.as_ptr()
+    }
+
+    /// Sets bit with index `index`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn set_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: Bit `index` is within bounds.
+        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Clears bit with index `index`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn clear_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: Bit `index` is within bounds.
+        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Replaces this [`Bitmap`] with `src` and sets any remaining bits to zero.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `src` is longer than this [`Bitmap`].
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
+    /// let short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
+    /// long_bitmap.copy_from_bitmap_and_extend(&short_bitmap);
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) {
+        assert!(
+            src.nbits <= self.nbits,
+            "Length of `src` must be <= {}, was {}",
+            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,
+            )
+        };
+    }
+
+    /// Replaces this bitmap with a prefix of `src` that fits into this [`Bitmap`].
+    ///
+    /// # Panics
+    ///
+    /// Panics if `src` is shorter than this [`Bitmap`].
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
+    /// let long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
+    /// short_bitmap.copy_prefix_from_bitmap(&long_bitmap);
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn copy_prefix_from_bitmap(&mut self, src: &Bitmap) {
+        assert!(
+            self.nbits <= src.nbits,
+            "Length of `src` must be >= {}, was {}",
+            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(),
+                self.nbits as u32,
+                self.nbits as u32,
+            )
+        };
+    }
+
+    /// Finds the last bit that is set.
+    #[inline]
+    pub fn find_last_bit(&self) -> Option<usize> {
+        // SAFETY: `nbits == 0` is supported and access is within bounds.
+        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+
+    /// Finds the next zero bit, starting from `offset`.
+    #[inline]
+    pub fn find_next_zero_bit(&self, offset: usize) -> Option<usize> {
+        // SAFETY: `nbits == 0` and out-of-bounds offset is supported.
+        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, offset) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+}
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.rc1.451.g8f38331e32-goog

[PATCH v4 3/3] Add DynamicIdPool Rust API.

[Burak Emir]

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

The file drivers/android/dbitmap.h uses bitmaps for allocating and
releasing IDs. We provide an equivalent Rust API that gives clients
fine-grained control over when to allocate a new bitmap.

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

diff --git a/MAINTAINERS b/MAINTAINERS
index b3bbce9274f0..d429ede24d3c 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4036,12 +4036,13 @@ F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
 BITMAP API [RUST]
-M:	Alice Ryhl <aliceryhl@google.com> (bitmap)
+M:	Alice Ryhl <aliceryhl@google.com> (bitmap,dynamic_id_pool)
 M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
 R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
 F:	rust/kernel/bitmap.rs
 F:	rust/kernel/cpumask.rs
+F:	rust/kernel/dynamic_id_pool.rs
 
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
diff --git a/rust/kernel/dynamic_id_pool.rs b/rust/kernel/dynamic_id_pool.rs
new file mode 100644
index 000000000000..3e243358cd6b
--- /dev/null
+++ b/rust/kernel/dynamic_id_pool.rs
@@ -0,0 +1,191 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+//! Rust API for an ID pool backed by a `Bitmap`.
+
+use crate::alloc::{AllocError, Flags};
+use crate::bitmap::Bitmap;
+
+/// Represents a dynamic ID pool backed by a `Bitmap`.
+///
+/// Clients acquire and release IDs from zero bits in a bitmap.
+///
+/// The ID pool can grow or shrink as needed. It has been designed
+/// to support the scenario where users need to control the time
+/// of allocation of a new backing bitmap, which may require release
+/// of locks.
+/// These operations then, are verified to determine if the grow or
+/// shrink is sill valid.
+///
+/// # Examples
+///
+/// Basic usage
+///
+/// ```
+/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+/// use kernel::dynamic_id_pool::DynamicIdPool;
+///
+/// let mut pool = DynamicIdPool::new(64, GFP_KERNEL)?;
+/// for i in 0..64 {
+///   pool.acquire_next_id(i).ok_or(ENOSPC)?;
+/// }
+/// assert_eq!(pool.acquire_next_id(63), None);
+/// let resizer = pool.grow_alloc().alloc(GFP_KERNEL)?;
+/// pool.grow(resizer);
+/// assert_eq!(pool.acquire_next_id(63), Some(64));
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Releasing spinlock to grow the pool
+///
+/// ```
+/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+/// use kernel::sync::{new_spinlock, SpinLock};
+/// use kernel::dynamic_id_pool::DynamicIdPool;
+///
+/// struct Example {
+///   pool: DynamicIdPool
+/// }
+///
+/// fn get_id_maybe_alloc(s: &SpinLock<Example>) -> Result<usize, AllocError> {
+///   let mut guard = s.lock();
+///   let mut resizer = None;
+///   loop {
+///     match guard.pool.acquire_next_id(0) {
+///       index @ Some(_) => return Ok(index),
+///       None => {
+///         let alloc_request = guard.pool.grow_alloc();
+///         drop(guard);
+///         let resizer = alloc_request.alloc(GFP_KERNEL)?;
+///         guard = s.lock();
+///         guard.pool.grow(resizer)
+///       }
+///     }
+///   }
+/// }
+/// ```
+pub struct DynamicIdPool {
+    map: Bitmap,
+}
+
+/// Returned when the `DynamicIdPool` should change size.
+pub struct AllocRequest {
+    nbits: usize,
+}
+
+/// Contains an allocated `Bitmap` for resizing `DynamicIdPool`.
+pub struct PoolResizer {
+    new: Bitmap,
+}
+
+impl AllocRequest {
+    /// Allocates a new `Bitmap` for `DynamicIdPool`.
+    pub fn alloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
+        let new = Bitmap::new(self.nbits, flags)?;
+        Ok(PoolResizer { new })
+    }
+}
+
+/// Minimum size we want to use for our backing `Bitmap`.
+const NBITS_MIN: usize = bindings::BITS_PER_LONG as usize;
+
+impl DynamicIdPool {
+    ///
+    #[inline]
+    pub fn new(mut nbits: usize, flags: Flags) -> Result<Self, AllocError> {
+        if nbits < NBITS_MIN {
+            nbits = NBITS_MIN
+        }
+        let map = Bitmap::new(nbits, flags)?;
+        Ok(Self { map })
+    }
+
+    /// Returns how many IDs this pool can currently have.
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.map.len()
+    }
+
+    /// Returns an `AllocRequest` if the can be shrunk, or None if not possible.
+    #[inline]
+    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
+        let len = self.map.len();
+        if len == NBITS_MIN {
+            return None
+        }
+        /*
+         * Determine if the bitmap can shrink based on the position of
+         * its last set bit. If the bit is within the first quarter of
+         * the bitmap then shrinking is possible. In this case, the
+         * bitmap should shrink to half its current size.
+         */
+        match self.map.find_last_bit() {
+            Some(bit) => {
+                if bit < (len >> 2) {
+                    Some(AllocRequest { nbits: len >> 1 })
+                } else {
+                    None
+                }
+            }
+            None => Some(AllocRequest { nbits: NBITS_MIN }),
+        }
+    }
+
+    /// Shrinks pool by using a new `Bitmap`, if still possible.
+    #[inline]
+    pub fn shrink(&mut self, mut resizer: PoolResizer) {
+        // Verify that shrinking is still possible. The `resizer`
+        // bitmap might have been allocated without locks, so this call
+        // could now be outdated. In this case, drop `resizer` and move on.
+        if let Some(AllocRequest { nbits }) = self.shrink_alloc() {
+            if nbits <= resizer.new.len() {
+                resizer.new.copy_prefix_from_bitmap(&self.map);
+                self.map = resizer.new;
+                return;
+            }
+        }
+    }
+
+    /// Returns an `AllocRequest` for growing this `DynamicIdPool`.
+    #[inline]
+    pub fn grow_alloc(&self) -> AllocRequest {
+        AllocRequest {
+            nbits: self.map.len() << 1,
+        }
+    }
+
+    /// Grows pool by using a new `Bitmap`, if still necessary.
+    #[inline]
+    pub fn grow(&mut self, mut resizer: PoolResizer) {
+        // `resizer` bitmap might have been allocated without locks,
+        // so this call could now be outdated. In this case, drop
+        // `resizer` and move on.
+        if resizer.new.len() <= self.map.len() {
+            return;
+        }
+
+        resizer.new.copy_from_bitmap_and_extend(&self.map);
+        self.map = resizer.new;
+    }
+
+    /// Acquires a new ID by finding and setting the next zero bit in the
+    /// bitmap. Upon success, returns its index. Otherwise, returns `None`
+    /// to indicate that a `grow_alloc` is needed.
+    #[inline]
+    pub fn acquire_next_id(&mut self, offset: usize) -> Option<usize> {
+        match self.map.find_next_zero_bit(offset) {
+            res @ Some(nr) => {
+                self.map.set_bit(nr);
+                res
+            }
+            None => None,
+        }
+    }
+
+    /// Releases an ID.
+    #[inline]
+    pub fn release_id(&mut self, id: usize) {
+        self.map.clear_bit(id);
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index be06ffc47473..4789e707dacc 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -47,6 +47,7 @@
 pub mod device_id;
 pub mod devres;
 pub mod driver;
+pub mod dynamic_id_pool;
 pub mod error;
 #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)]
 pub mod firmware;
-- 
2.49.0.rc1.451.g8f38331e32-goog

Re: [PATCH v4 1/3] Adds bitmap.c and bitops.c Rust bindings.

[Yury Norov]

On Tue, Mar 18, 2025 at 05:45:45PM +0000, Burak Emir wrote:
> Adds helpers for bitmap.c and bitops.c to get Rust bindings
> for inline methods __set_bit and __clear_bit (these are
> non-atomic variants) as well as bitmap_copy_and_extend.
> 
> These are needed for providing a basic Rust Bitmap API.
> Update MAINTAINERS.
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
>  MAINTAINERS                     | 11 +++++++++++
>  rust/bindings/bindings_helper.h |  1 +
>  rust/helpers/bitmap.c           |  9 +++++++++
>  rust/helpers/bitops.c           | 13 +++++++++++++
>  rust/helpers/helpers.c          |  2 ++
>  5 files changed, 36 insertions(+)
>  create mode 100644 rust/helpers/bitmap.c
>  create mode 100644 rust/helpers/bitops.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index c43d66bd85f3..50f44d7e5c6e 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4029,6 +4029,12 @@ F:	tools/include/vdso/bits.h
>  F:	tools/lib/bitmap.c
>  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

Are you sure you wrote it yourself? I checked next-20250318 quickly
and found it was me!

Please build your work on top of -next as soon as you need those
bindings.

> +
>  BITMAP API [RUST]
>  M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
>  R:	Yury Norov <yury.norov@gmail.com>
> @@ -4049,6 +4055,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

Please make it a separate patch. That way I'll be able to ACK only
this record.

> +
>  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 55354e4dec14..6bd4396b9cd3 100644
> --- a/rust/bindings/bindings_helper.h
> +++ b/rust/bindings/bindings_helper.h
> @@ -7,6 +7,7 @@
>   */
>  
>  #include <kunit/test.h>
> +#include <linux/bitmap.h>
>  #include <linux/blk-mq.h>
>  #include <linux/blk_types.h>
>  #include <linux/blkdev.h>
> diff --git a/rust/helpers/bitmap.c b/rust/helpers/bitmap.c
> new file mode 100644
> index 000000000000..a50e2f082e47
> --- /dev/null
> +++ b/rust/helpers/bitmap.c
> @@ -0,0 +1,9 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/bitmap.h>
> +
> +void rust_helper_bitmap_copy_and_extend(unsigned long *to, const unsigned long *from,
> +		unsigned int count, unsigned int size)
> +{
> +	bitmap_copy_and_extend(to, from, count, size);
> +}
> diff --git a/rust/helpers/bitops.c b/rust/helpers/bitops.c
> new file mode 100644
> index 000000000000..0ea1611b95dc
> --- /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, unsigned long *addr)
> +{
> +	__set_bit(nr, addr);
> +}
> +
> +void rust_helper___clear_bit(unsigned int nr, unsigned long *addr)
> +{
> +	__clear_bit(nr, addr);
> +}
> diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c
> index 0640b7e115be..74e5e10694a4 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"
> -- 
> 2.49.0.rc1.451.g8f38331e32-goog

Re: [PATCH v4 2/3] Adds Rust Bitmap API.

[Yury Norov]

On Tue, Mar 18, 2025 at 05:51:53PM +0000, Burak Emir wrote:
> Provides an abstraction for C bitmap API and bitops operations.
> This includes enough functionality to reimplementing a Binder
> data structure (drivers/android/dbitmap.h). More methods can be
> added later. We offer a safe API through bounds checks which
> panic if violated.
> 
> We use the `usize` type for sizes and indices into the bitmap,
> because Rust generally always uses that type for indices and lengths
> and it will be more convenient if the API accepts that type. This means
> that we need to perform some casts to/from u32 and usize, since the C
> headers use unsigned int instead of size_t/unsigned long for these
> numbers in some places.
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
>  MAINTAINERS           |   2 +
>  rust/kernel/bitmap.rs | 234 ++++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs    |   1 +
>  3 files changed, 237 insertions(+)
>  create mode 100644 rust/kernel/bitmap.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 50f44d7e5c6e..b3bbce9274f0 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4036,9 +4036,11 @@ F:	rust/helpers/bitmap.c
>  F:	rust/helpers/cpumask.c
>  
>  BITMAP API [RUST]
> +M:	Alice Ryhl <aliceryhl@google.com> (bitmap)
>  M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
>  R:	Yury Norov <yury.norov@gmail.com>
>  S:	Maintained
> +F:	rust/kernel/bitmap.rs
>  F:	rust/kernel/cpumask.rs

If you guys are not ready to maintain this as a whole, please split
the record. scripts/get_maintainers doesn't honor this specifications,
and you will anyways receive all the bitmaps traffic.

I checked the existing records:

  $ grep ^M: MAINTAINERS | grep \(
  M:	Ji-Ze Hong (Peter Hong) <peter_hong@fintek.com.tw>
  M:	Boqun Feng <boqun.feng@gmail.com> (LOCKDEP & RUST)
  M:	"Richard Russon (FlatCap)" <ldm@flatcap.org>
  M:	Matthew Wilcox (Oracle) <willy@infradead.org>
  M:	Frederic Weisbecker <frederic@kernel.org> (kernel/rcu/tree_nocb.h)
  M:	Neeraj Upadhyay <neeraj.upadhyay@kernel.org> (kernel/rcu/tasks.h)
  M:	Juri Lelli <juri.lelli@redhat.com> (SCHED_DEADLINE)
  M:	Vincent Guittot <vincent.guittot@linaro.org> (SCHED_NORMAL)

As you see, it's not a common practice - only scheduler and RCU people
do that. And I don't find this practice healthy.
  
>  BITOPS API
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> new file mode 100644
> index 000000000000..e8117e0dbe05
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,234 @@
> +// 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;
> +
> +/// Represents a bitmap.
> +///
> +/// Wraps underlying C bitmap API.
> +///
> +/// # Examples
> +///
> +/// Basic usage
> +/// ```
> +/// use kernel::alloc::flags::GFP_KERNEL;
> +/// use kernel::bitmap::Bitmap;
> +///
> +/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
> +/// assert_eq!(16, b.len());
> +/// for i in 0..16 {
> +///   if i % 4 == 0 {
> +///     b.set_bit(i);
> +///   }
> +/// }
> +/// assert_eq!(Some(1), b.find_next_zero_bit(0));
> +/// assert_eq!(Some(5), b.find_next_zero_bit(5));
> +/// assert_eq!(Some(12), b.find_last_bit());
> +/// # Ok::<(), Error>(())
> +/// ```
> +///
> +/// # 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.
> +/// `nbits` is `<= u32::MAX` and never changes.
> +pub struct Bitmap {
> +    /// Pointer to an array of `unsigned long`.
> +    ptr: NonNull<usize>,
> +    /// How many bits this bitmap stores. Must be `<= u32::MAX`.

Must be <= i32:MAX - I already told that. For 'how many bits' we have a
special word: length.

> +    nbits: usize,
> +}
> +
> +impl Drop for Bitmap {
> +    fn drop(&mut self) {
> +        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
> +        //
> +        // INVARIANT: there is no other use of the `self.ptr` after this
> +        // call and the value is being dropped so the broken invariant is
> +        // not observable on function exit.
> +        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
> +    }
> +}
> +
> +impl Bitmap {
> +    /// Constructs a new [`Bitmap`].
> +    ///
> +    /// Fails with [`AllocError`] when the [`Bitmap`] could not be
> +    /// allocated. This includes the case when `nbits` is greater
> +    /// than `u32::MAX`.
> +    #[inline]
> +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {

Are those 'drop' and 'new' something like a special rust words? If not -
can you use alloc and free wording? Would be nice to have rust part
looking similar to C. Nobody wants to keep two sets of names in mind.

> +        if let Ok(nbits_u32) = u32::try_from(nbits) {
> +            // SAFETY: `nbits == 0` is permitted and `nbits <= u32::MAX`.
> +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> +            // Zero-size allocation is ok and yields a dangling pointer.

Maybe it's OK, but I'm not aware of any a correct algorithm that needs
0-sized bitmaps. I already asked for it on previous iteration, right?
So unless you can show me such an example and explain what for you need
0-sized bitmaps, please drop this wording.

> +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> +            // INVARIANT: ptr returned by C `bitmap_zalloc` and nbits checked.
> +            Ok(Bitmap { ptr, nbits })
> +        } else {
> +            Err(AllocError)
> +        }
> +    }
> +
> +    /// Returns how many bits this [`Bitmap`] holds.

This 'how many bits' may read wrong like 'how many set bits'. Refer
find_first_bit() for example. Please use the word 'length'.

> +    #[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
> +    }

Please no. We already have bitmap_empty() with the meaning: no set bits.
I really don't understand why are you guys so worrying about this very
specific and most likely erroneous case...

This function is not even used in the following patch. Really don't
need it.

> +
> +    /// Returns a mutable raw pointer to the backing [`Bitmap`].
> +    #[inline]
> +    fn as_mut_ptr(&mut self) -> *mut usize {
> +        self.ptr.as_ptr()
> +    }
> +
> +    /// Returns a raw pointer to the backing [`Bitmap`].
> +    #[inline]
> +    fn as_ptr(&self) -> *const usize {
> +        self.ptr.as_ptr()
> +    }
> +
> +    /// Sets bit with index `index`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn set_bit(&mut self, index: usize) {

set_bit() is an atomic name, but you wire it to a non-atomic operation.
This is a mess.

> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: Bit `index` is within bounds.
> +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Clears bit with index `index`.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn clear_bit(&mut self, index: usize) {
> +        assert!(
> +            index < self.nbits,
> +            "Bit `index` must be < {}, was {}",
> +            self.nbits,
> +            index
> +        );
> +        // SAFETY: Bit `index` is within bounds.
> +        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Replaces this [`Bitmap`] with `src` and sets any remaining bits to zero.

Please: replace and set, not replaces and sets.

> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `src` is longer than this [`Bitmap`].
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> +    /// let short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> +    /// long_bitmap.copy_from_bitmap_and_extend(&short_bitmap);
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) {

Let's make it a rule: if you pick a function from C code as-is, you
pick the name as-is, too. I'm OK if you will want to drop the 'bitmap'
prefix, because it's a method. But I want to be able to just grep the
name and find its roots in C.

> +        assert!(
> +            src.nbits <= self.nbits,
> +            "Length of `src` must be <= {}, was {}",
> +            self.nbits,
> +            src.nbits
> +        );
> +        // SAFETY: `nbits == 0` is supported and access to `self` and `src` is within bounds.

I don't understand this. If nbits == 0, there's nothing to access. Can
you instead say "handled properly by the C function", or something?

> +        unsafe {
> +            bindings::bitmap_copy_and_extend(
> +                self.as_mut_ptr(),
> +                src.as_ptr(),
> +                src.nbits as u32,
> +                self.nbits as u32,
> +            )
> +        };
> +    }
> +
> +    /// Replaces this bitmap with a prefix of `src` that fits into this [`Bitmap`].
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `src` is shorter than this [`Bitmap`].
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> +    /// let long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> +    /// short_bitmap.copy_prefix_from_bitmap(&long_bitmap);
> +    /// # Ok::<(), AllocError>(())

Why don't you make it a real test? I asked for tests on previous
round, but I didn't think that you will make me to construct the
test myself from scattered pieces of commented code in a foreign
language.

> +    /// ```
> +    #[inline]
> +    pub fn copy_prefix_from_bitmap(&mut self, src: &Bitmap) {

Are you sure you need this 2nd function? It's almost the same as the
previous one. If the first one works like a.copy_and_extend(b), then
this one is simply b.copy_and_extend(a). Or I misunderstand this?

And anyways, this 'copy_prefix_from' thing is confusing and
misleading. There are no prefixes in bitmaps.

> +        assert!(
> +            self.nbits <= src.nbits,
> +            "Length of `src` must be >= {}, was {}",
> +            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(),
> +                self.nbits as u32,
> +                self.nbits as u32,
> +            )
> +        };
> +    }
> +
> +    /// Finds the last bit that is set.
> +    #[inline]
> +    pub fn find_last_bit(&self) -> Option<usize> {

You may drop the 'find' prefix because it's a method.

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

No panics anymore? I recall Alice said you need them for hardening...

> +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> +        if index == self.nbits {
> +            None
> +        } else {
> +            Some(index)
> +        }
> +    }
> +
> +    /// Finds the next zero bit, starting from `offset`.
> +    #[inline]
> +    pub fn find_next_zero_bit(&self, offset: usize) -> Option<usize> {
> +        // SAFETY: `nbits == 0` and out-of-bounds offset is supported.

It's not supported. The request with such parameters is ignored,
and >= nbits is returned.

> +        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, offset) };
> +        if index == self.nbits {
> +            None
> +        } else {
> +            Some(index)
> +        }
> +    }
> +}
> 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.rc1.451.g8f38331e32-goog

Re: [PATCH v4 2/3] Adds Rust Bitmap API.

[Alice Ryhl]

On Tue, Mar 18, 2025 at 04:17:18PM -0400, Yury Norov wrote:
> On Tue, Mar 18, 2025 at 05:51:53PM +0000, Burak Emir wrote:
> > Provides an abstraction for C bitmap API and bitops operations.
> > This includes enough functionality to reimplementing a Binder
> > data structure (drivers/android/dbitmap.h). More methods can be
> > added later. We offer a safe API through bounds checks which
> > panic if violated.
> > 
> > We use the `usize` type for sizes and indices into the bitmap,
> > because Rust generally always uses that type for indices and lengths
> > and it will be more convenient if the API accepts that type. This means
> > that we need to perform some casts to/from u32 and usize, since the C
> > headers use unsigned int instead of size_t/unsigned long for these
> > numbers in some places.
> > 
> > Suggested-by: Alice Ryhl <aliceryhl@google.com>
> > Signed-off-by: Burak Emir <bqe@google.com>
> > ---
> >  MAINTAINERS           |   2 +
> >  rust/kernel/bitmap.rs | 234 ++++++++++++++++++++++++++++++++++++++++++
> >  rust/kernel/lib.rs    |   1 +
> >  3 files changed, 237 insertions(+)
> >  create mode 100644 rust/kernel/bitmap.rs
> > 
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index 50f44d7e5c6e..b3bbce9274f0 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -4036,9 +4036,11 @@ F:	rust/helpers/bitmap.c
> >  F:	rust/helpers/cpumask.c
> >  
> >  BITMAP API [RUST]
> > +M:	Alice Ryhl <aliceryhl@google.com> (bitmap)
> >  M:	Viresh Kumar <viresh.kumar@linaro.org> (cpumask)
> >  R:	Yury Norov <yury.norov@gmail.com>
> >  S:	Maintained
> > +F:	rust/kernel/bitmap.rs
> >  F:	rust/kernel/cpumask.rs
> 
> If you guys are not ready to maintain this as a whole, please split
> the record. scripts/get_maintainers doesn't honor this specifications,
> and you will anyways receive all the bitmaps traffic.
> 
> I checked the existing records:
> 
>   $ grep ^M: MAINTAINERS | grep \(
>   M:	Ji-Ze Hong (Peter Hong) <peter_hong@fintek.com.tw>
>   M:	Boqun Feng <boqun.feng@gmail.com> (LOCKDEP & RUST)
>   M:	"Richard Russon (FlatCap)" <ldm@flatcap.org>
>   M:	Matthew Wilcox (Oracle) <willy@infradead.org>
>   M:	Frederic Weisbecker <frederic@kernel.org> (kernel/rcu/tree_nocb.h)
>   M:	Neeraj Upadhyay <neeraj.upadhyay@kernel.org> (kernel/rcu/tasks.h)
>   M:	Juri Lelli <juri.lelli@redhat.com> (SCHED_DEADLINE)
>   M:	Vincent Guittot <vincent.guittot@linaro.org> (SCHED_NORMAL)
> 
> As you see, it's not a common practice - only scheduler and RCU people
> do that. And I don't find this practice healthy.

Sounds reasonable enough.

> >  BITOPS API
> > diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> > new file mode 100644
> > index 000000000000..e8117e0dbe05
> > --- /dev/null
> > +++ b/rust/kernel/bitmap.rs
> > @@ -0,0 +1,234 @@
> > +// 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;
> > +
> > +/// Represents a bitmap.
> > +///
> > +/// Wraps underlying C bitmap API.
> > +///
> > +/// # Examples
> > +///
> > +/// Basic usage
> > +/// ```
> > +/// use kernel::alloc::flags::GFP_KERNEL;
> > +/// use kernel::bitmap::Bitmap;
> > +///
> > +/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
> > +/// assert_eq!(16, b.len());
> > +/// for i in 0..16 {
> > +///   if i % 4 == 0 {
> > +///     b.set_bit(i);
> > +///   }
> > +/// }
> > +/// assert_eq!(Some(1), b.find_next_zero_bit(0));
> > +/// assert_eq!(Some(5), b.find_next_zero_bit(5));
> > +/// assert_eq!(Some(12), b.find_last_bit());
> > +/// # Ok::<(), Error>(())
> > +/// ```
> > +///
> > +/// # 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.
> > +/// `nbits` is `<= u32::MAX` and never changes.
> > +pub struct Bitmap {
> > +    /// Pointer to an array of `unsigned long`.
> > +    ptr: NonNull<usize>,
> > +    /// How many bits this bitmap stores. Must be `<= u32::MAX`.
> 
> Must be <= i32:MAX - I already told that. For 'how many bits' we have a
> special word: length.

Sorry I think we forgot to fix this to be i32.

> > +    nbits: usize,
> > +}
> > +
> > +impl Drop for Bitmap {
> > +    fn drop(&mut self) {
> > +        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
> > +        //
> > +        // INVARIANT: there is no other use of the `self.ptr` after this
> > +        // call and the value is being dropped so the broken invariant is
> > +        // not observable on function exit.
> > +        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
> > +    }
> > +}
> > +
> > +impl Bitmap {
> > +    /// Constructs a new [`Bitmap`].
> > +    ///
> > +    /// Fails with [`AllocError`] when the [`Bitmap`] could not be
> > +    /// allocated. This includes the case when `nbits` is greater
> > +    /// than `u32::MAX`.
> > +    #[inline]
> > +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> 
> Are those 'drop' and 'new' something like a special rust words? If not -
> can you use alloc and free wording? Would be nice to have rust part
> looking similar to C. Nobody wants to keep two sets of names in mind.

Rewording `new` to `alloc` seems reasonable.

As for "drop", that word is special. It's the destructor that is called
automatically when the bitmap goes out of scope - you can't call it
directly. It must be called "drop".

> > +        if let Ok(nbits_u32) = u32::try_from(nbits) {
> > +            // SAFETY: `nbits == 0` is permitted and `nbits <= u32::MAX`.
> > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > +            // Zero-size allocation is ok and yields a dangling pointer.
> 
> Maybe it's OK, but I'm not aware of any a correct algorithm that needs
> 0-sized bitmaps. I already asked for it on previous iteration, right?
> So unless you can show me such an example and explain what for you need
> 0-sized bitmaps, please drop this wording.

Thinking about it, I actually think there is a good reason to support
zero-sized bitmaps for the Binder use-case. Right now, we always
allocate at least one long worth of bits even if they're all 0. But we
can improve the memory usage of this code by not allocating any memory
for the bitmap until the first time we use it.

The reason that dbitmap.h doesn't do this is historical. Originally, the
bitmap started out having BIT(0) set to 1, so we needed an allocation to
hold that from the very beginning. But that was changed in commit
11512c197d38 ("binder: fix descriptor lookup for context manager"), so
the bitmap now starts out empty.

> > +            let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> > +            // INVARIANT: ptr returned by C `bitmap_zalloc` and nbits checked.
> > +            Ok(Bitmap { ptr, nbits })
> > +        } else {
> > +            Err(AllocError)
> > +        }
> > +    }
> > +
> > +    /// Returns how many bits this [`Bitmap`] holds.
> 
> This 'how many bits' may read wrong like 'how many set bits'. Refer
> find_first_bit() for example. Please use the word 'length'.

Reasonable, we will reword to use "length".

> > +    #[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
> > +    }
> 
> Please no. We already have bitmap_empty() with the meaning: no set bits.
> I really don't understand why are you guys so worrying about this very
> specific and most likely erroneous case...
> 
> This function is not even used in the following patch. Really don't
> need it.

The clippy linter emits a warning if you have a `len` method but don't
have an `is_empty` method, since Rust containers usually have both.

https://rust-lang.github.io/rust-clippy/master/index.html#len_without_is_empty

But the confusion with "no set bits" seems like a good reason to silence
that warning for bitmap.

> > +    /// Sets bit with index `index`.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn set_bit(&mut self, index: usize) {
> 
> set_bit() is an atomic name, but you wire it to a non-atomic operation.
> This is a mess.

Hmm. I do generally agree that we should try to match C names, but I'm
unsure about this particular case due to the underscores.

This method takes "&mut self" rather than "&self", which means that the
caller must have exclusive access to the bitmap to call this method.
Attempting to call it when the bitmap is shared will result in a
compilation failure, so it is impossible to call the non-atomic method
in cases where you must use the atomic version.

We could call this method __set_bit, but using underscore prefixes for
methods is very very rare in Rust code because prefixing a name with an
underscore usually means "do not emit warnings if this thing is unused".
For example, when locking a mutex, you might write this:

{
    let _lock = my_mutex.lock();
    // do stuff ...

    // _lock goes out of scope here, unlocking the mutex
}

Here, if you called the variable "lock" you would get an unused variable
warning, but prefixing the variable name with an underscore silences
that warning.

We can still call the method __set_bit if you think that is best, but
because underscore prefixes usually mean something different in Rust, I
wonder if we should use slightly different names in Rust. Thoughts?

> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: Bit `index` is within bounds.
> > +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> > +    }
> > +
> > +    /// Clears bit with index `index`.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn clear_bit(&mut self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
> > +        // SAFETY: Bit `index` is within bounds.
> > +        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
> > +    }
> > +
> > +    /// Replaces this [`Bitmap`] with `src` and sets any remaining bits to zero.
> 
> Please: replace and set, not replaces and sets.
> 
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `src` is longer than this [`Bitmap`].
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +    /// use kernel::bitmap::Bitmap;
> > +    ///
> > +    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> > +    /// let short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> > +    /// long_bitmap.copy_from_bitmap_and_extend(&short_bitmap);
> > +    /// # Ok::<(), AllocError>(())
> > +    /// ```
> > +    #[inline]
> > +    pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) {
> 
> Let's make it a rule: if you pick a function from C code as-is, you
> pick the name as-is, too. I'm OK if you will want to drop the 'bitmap'
> prefix, because it's a method. But I want to be able to just grep the
> name and find its roots in C.
> 
> > +        assert!(
> > +            src.nbits <= self.nbits,
> > +            "Length of `src` must be <= {}, was {}",
> > +            self.nbits,
> > +            src.nbits
> > +        );
> > +        // SAFETY: `nbits == 0` is supported and access to `self` and `src` is within bounds.
> 
> I don't understand this. If nbits == 0, there's nothing to access. Can
> you instead say "handled properly by the C function", or something?
> 
> > +        unsafe {
> > +            bindings::bitmap_copy_and_extend(
> > +                self.as_mut_ptr(),
> > +                src.as_ptr(),
> > +                src.nbits as u32,
> > +                self.nbits as u32,
> > +            )
> > +        };
> > +    }
> > +
> > +    /// Replaces this bitmap with a prefix of `src` that fits into this [`Bitmap`].
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `src` is shorter than this [`Bitmap`].
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> > +    /// use kernel::bitmap::Bitmap;
> > +    ///
> > +    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> > +    /// let long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> > +    /// short_bitmap.copy_prefix_from_bitmap(&long_bitmap);
> > +    /// # Ok::<(), AllocError>(())
> 
> Why don't you make it a real test? I asked for tests on previous
> round, but I didn't think that you will make me to construct the
> test myself from scattered pieces of commented code in a foreign
> language.

Documentation examples are real kunit tests. If you run the kunit tests,
this code will run, and the kunit test will fail if the assertion inside
this method is triggered.

> > +    /// ```
> > +    #[inline]
> > +    pub fn copy_prefix_from_bitmap(&mut self, src: &Bitmap) {
> 
> Are you sure you need this 2nd function? It's almost the same as the
> previous one. If the first one works like a.copy_and_extend(b), then
> this one is simply b.copy_and_extend(a). Or I misunderstand this?
> 
> And anyways, this 'copy_prefix_from' thing is confusing and
> misleading. There are no prefixes in bitmaps.

Hmm, maybe we don't need both. We could use min(self.nbits, src.nbits)
as the third argument. Or we could take it as an argument and assert
that it's in bounds for both lengths.

> > +        assert!(
> > +            self.nbits <= src.nbits,
> > +            "Length of `src` must be >= {}, was {}",
> > +            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(),
> > +                self.nbits as u32,
> > +                self.nbits as u32,
> > +            )
> > +        };
> > +    }
> > +
> > +    /// Finds the last bit that is set.
> > +    #[inline]
> > +    pub fn find_last_bit(&self) -> Option<usize> {
> 
> You may drop the 'find' prefix because it's a method.
> 
> > +        // SAFETY: `nbits == 0` is supported and access is within bounds.
> 
> No panics anymore? I recall Alice said you need them for hardening...

For the specific case of finding the last bit, no panics is correct.
This method returns the index of the last bit if there is a last bit.
Otherwise, if all bits are 0, it returns None. This lets the caller
handle both cases.

Burak, let's add this example:

match bitmap.last_bit() {
    Some(idx) => {
        pr_info!("The last bit has index {idx}.\n");
    }
    None => {
        pr_info!("All bits in this bitmap are 0.\n");
    }
}

> > +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> > +        if index == self.nbits {
> > +            None
> > +        } else {
> > +            Some(index)
> > +        }
> > +    }
> > +
> > +    /// Finds the next zero bit, starting from `offset`.
> > +    #[inline]
> > +    pub fn find_next_zero_bit(&self, offset: usize) -> Option<usize> {
> > +        // SAFETY: `nbits == 0` and out-of-bounds offset is supported.
> 
> It's not supported. The request with such parameters is ignored,
> and >= nbits is returned.
> 
> > +        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, offset) };
> > +        if index == self.nbits {
> > +            None
> > +        } else {
> > +            Some(index)
> > +        }
> > +    }
> > +}
> > 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.rc1.451.g8f38331e32-goog

Re: [PATCH v4 2/3] Adds Rust Bitmap API.

[Miguel Ojeda]

On Wed, Mar 19, 2025 at 11:40 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> Rewording `new` to `alloc` seems reasonable.
>
> As for "drop", that word is special. It's the destructor that is called
> automatically when the bitmap goes out of scope - you can't call it
> directly. It must be called "drop".

Alice obviously knows the following, but for so that Yury has the
context: `new` is the typical name in Rust for the "primary"
constructor, so that is probably Burak picked it, e.g. see:

    https://rust-lang.github.io/api-guidelines/predictability.html#constructors-are-static-inherent-methods-c-ctor

Constructors in Rust are not special, and you can use any names (and
can return errors etc., unlike C++).

So people use `new` by convention since it is what others may look for
first in the documentation. It is especially nice if there is only a
single constructor, but not a big deal.

> But the confusion with "no set bits" seems like a good reason to silence
> that warning for bitmap.

Yeah, if a lint is giving trouble, please just disable it.

And if we need to disable it in quite a few places, we may just want
to disable it globally.

> We can still call the method __set_bit if you think that is best, but
> because underscore prefixes usually mean something different in Rust, I
> wonder if we should use slightly different names in Rust. Thoughts?

I would really prefer if we do our best to avoid underscores in Rust,
especially for non-private APIs.

In Linux we abuse `_+names` a bit sometimes to avoid writing a proper
name/prefix/suffix for the different variations of operations, and I
don't think it is a good idea to mimic that for non-private APIs. I
mean, for static single variations, it is OK-ish, but other cases are
not really great.

Worse, if we start doing that in Rust, we may start doing it for
things that do not even need to mimic a C API name...

Now, I know it is painful to have a different name than C, so it is a
trade-off. And sometimes coming up with names is difficult, too.

The underscore implying "possibly unused" is not too important for
`pub` APIs I think, since the compiler wouldn't warn about those
anyway, no? But for non-`pub` ones, I agree it is one more reason to
avoid it.

Cheers,
Miguel

Re: [PATCH v4 2/3] Adds Rust Bitmap API.

[Yury Norov]

On Wed, Mar 19, 2025 at 10:39:57AM +0000, Alice Ryhl wrote:
> On Tue, Mar 18, 2025 at 04:17:18PM -0400, Yury Norov wrote:
> > On Tue, Mar 18, 2025 at 05:51:53PM +0000, Burak Emir wrote:

[...]

> > Are those 'drop' and 'new' something like a special rust words? If not -
> > can you use alloc and free wording? Would be nice to have rust part
> > looking similar to C. Nobody wants to keep two sets of names in mind.
> 
> Rewording `new` to `alloc` seems reasonable.
> 
> As for "drop", that word is special. It's the destructor that is called
> automatically when the bitmap goes out of scope - you can't call it
> directly. It must be called "drop".

OK, then drop and new.

> > > +        if let Ok(nbits_u32) = u32::try_from(nbits) {
> > > +            // SAFETY: `nbits == 0` is permitted and `nbits <= u32::MAX`.
> > > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > > +            // Zero-size allocation is ok and yields a dangling pointer.
> > 
> > Maybe it's OK, but I'm not aware of any a correct algorithm that needs
> > 0-sized bitmaps. I already asked for it on previous iteration, right?
> > So unless you can show me such an example and explain what for you need
> > 0-sized bitmaps, please drop this wording.
> 
> Thinking about it, I actually think there is a good reason to support
> zero-sized bitmaps for the Binder use-case. Right now, we always
> allocate at least one long worth of bits even if they're all 0. But we
> can improve the memory usage of this code by not allocating any memory
> for the bitmap until the first time we use it.
> 
> The reason that dbitmap.h doesn't do this is historical. Originally, the
> bitmap started out having BIT(0) set to 1, so we needed an allocation to
> hold that from the very beginning. But that was changed in commit
> 11512c197d38 ("binder: fix descriptor lookup for context manager"), so
> the bitmap now starts out empty.

Empty bitmap is not a 0-length bitmap, right?

If it was me inventing dynamic bitmaps, and if I was concerned about
usability and performance, I would think carefully what exactly the
request for 0-bits Bitmap object means.

I would probably consider it as a caller error, which makes total
sense.

Or I would consider it as a special hint, like 'give me something to
begin with'.

If I decided to go with the 2nd option, I'd probably avoid memory
allocation at all, and re-use the pointer as the bitmap of the length
BITS_PER_LONG. That would save _a lot_ on useless small kmalloc()
calls.

The whole business of dynamic arrays is about potentially infinite
number of elements. User of your array doesn't even care about the
exact length, because it may get changed anytime, right?

In that case, the comment would sound like:

  // Zero-size Bitmap request yields a bitmap of an arbitrary
  // non-zero length.

[...]
 
> The clippy linter emits a warning if you have a `len` method but don't
> have an `is_empty` method, since Rust containers usually have both.
> 
> https://rust-lang.github.io/rust-clippy/master/index.html#len_without_is_empty
> 
> But the confusion with "no set bits" seems like a good reason to silence
> that warning for bitmap.
 
So the comment at your link says:

 It is good custom to have both methods, because for some data structures,
 asking about the length will be a costly operation, whereas .is_empty()
 can usually answer in constant time.

In this case both len() and is_empty() are O(1), but the last one
is totally misleading.

You guys would better teach your linter to understand when the len()
is cheap, so is_empty() is useless.

> > > +    /// Sets bit with index `index`.
> > > +    ///
> > > +    /// # Panics
> > > +    ///
> > > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > > +    #[inline]
> > > +    pub fn set_bit(&mut self, index: usize) {
> > 
> > set_bit() is an atomic name, but you wire it to a non-atomic operation.
> > This is a mess.
> 
> Hmm. I do generally agree that we should try to match C names, but I'm
> unsure about this particular case due to the underscores.
> 
> This method takes "&mut self" rather than "&self", which means that the
> caller must have exclusive access to the bitmap to call this method.
> Attempting to call it when the bitmap is shared will result in a
> compilation failure, so it is impossible to call the non-atomic method
> in cases where you must use the atomic version.

Does mutual access implies memory barriers? Your code doesn't add
them. Is rust compiler so smart to realize that you need it?

I mean the following scenario:

CPU1                            CPU2
a.set_bit(1)
                                a.test_bit(1) -> 0
cache_flush()
                                a.test_bit(1) -> 1

If the above is impossible, then yes, your set_bit is atomic.

> We could call this method __set_bit, but using underscore prefixes for
> methods is very very rare in Rust code because prefixing a name with an
> underscore usually means "do not emit warnings if this thing is unused".
> For example, when locking a mutex, you might write this:
> 
> {
>     let _lock = my_mutex.lock();
>     // do stuff ...
> 
>     // _lock goes out of scope here, unlocking the mutex
> }
> 
> Here, if you called the variable "lock" you would get an unused variable
> warning, but prefixing the variable name with an underscore silences
> that warning.

But underscored method is not a local underscored variable. It doesn't
have scope.

> We can still call the method __set_bit if you think that is best, but

No I don't. Nobody likes underscored notation for non-atomic bit ops,
but it's a historical thing.

> because underscore prefixes usually mean something different in Rust, I
> wonder if we should use slightly different names in Rust. Thoughts?

This is a new project, and you may decide to change notation. Just
please be very specific about it.

So I'd suggest the following:

1. Mirror C interface: __set_bit() and set_bit()
2. set_bit_nonatomic() and set_bit()
3. set_bit() and set_bit_atomic()

The last one looks the best to me, except that it just the opposite
to what people got used to in Linux. If you go with #3, please add
both atomic and non-atomic set_bit()s in the same patch, together with
a bunch of comments, so people will be aware.

> > > +        assert!(
> > > +            index < self.nbits,
> > > +            "Bit `index` must be < {}, was {}",
> > > +            self.nbits,
> > > +            index
> > > +        );
> > > +        // SAFETY: Bit `index` is within bounds.
> > > +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> > > +    }
> > > +
> > > +    /// Clears bit with index `index`.
> > > +    ///
> > > +    /// # Panics
> > > +    ///
> > > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > > +    #[inline]
> > > +    pub fn clear_bit(&mut self, index: usize) {
> > > +        assert!(
> > > +            index < self.nbits,
> > > +            "Bit `index` must be < {}, was {}",
> > > +            self.nbits,
> > > +            index
> > > +        );
> > > +        // SAFETY: Bit `index` is within bounds.
> > > +        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
> > > +    }
> > > +
> > > +    /// Replaces this [`Bitmap`] with `src` and sets any remaining bits to zero.
> > 
> > Please: replace and set, not replaces and sets.

Also, bitmap_replace() is an existing function. It's better to avoid
that word in different context at all.

Re: [PATCH v4 2/3] Adds Rust Bitmap API.

[Alice Ryhl]

On Wed, Mar 19, 2025 at 10:31:12AM -0400, Yury Norov wrote:
> On Wed, Mar 19, 2025 at 10:39:57AM +0000, Alice Ryhl wrote:
> > On Tue, Mar 18, 2025 at 04:17:18PM -0400, Yury Norov wrote:
> > > On Tue, Mar 18, 2025 at 05:51:53PM +0000, Burak Emir wrote:
> 
> [...]
> 
> > > Are those 'drop' and 'new' something like a special rust words? If not -
> > > can you use alloc and free wording? Would be nice to have rust part
> > > looking similar to C. Nobody wants to keep two sets of names in mind.
> > 
> > Rewording `new` to `alloc` seems reasonable.
> > 
> > As for "drop", that word is special. It's the destructor that is called
> > automatically when the bitmap goes out of scope - you can't call it
> > directly. It must be called "drop".
> 
> OK, then drop and new.
> 
> > > > +        if let Ok(nbits_u32) = u32::try_from(nbits) {
> > > > +            // SAFETY: `nbits == 0` is permitted and `nbits <= u32::MAX`.
> > > > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > > > +            // Zero-size allocation is ok and yields a dangling pointer.
> > > 
> > > Maybe it's OK, but I'm not aware of any a correct algorithm that needs
> > > 0-sized bitmaps. I already asked for it on previous iteration, right?
> > > So unless you can show me such an example and explain what for you need
> > > 0-sized bitmaps, please drop this wording.
> > 
> > Thinking about it, I actually think there is a good reason to support
> > zero-sized bitmaps for the Binder use-case. Right now, we always
> > allocate at least one long worth of bits even if they're all 0. But we
> > can improve the memory usage of this code by not allocating any memory
> > for the bitmap until the first time we use it.
> > 
> > The reason that dbitmap.h doesn't do this is historical. Originally, the
> > bitmap started out having BIT(0) set to 1, so we needed an allocation to
> > hold that from the very beginning. But that was changed in commit
> > 11512c197d38 ("binder: fix descriptor lookup for context manager"), so
> > the bitmap now starts out empty.
> 
> Empty bitmap is not a 0-length bitmap, right?
> 
> If it was me inventing dynamic bitmaps, and if I was concerned about
> usability and performance, I would think carefully what exactly the
> request for 0-bits Bitmap object means.
> 
> I would probably consider it as a caller error, which makes total
> sense.
> 
> Or I would consider it as a special hint, like 'give me something to
> begin with'.
> 
> If I decided to go with the 2nd option, I'd probably avoid memory
> allocation at all, and re-use the pointer as the bitmap of the length
> BITS_PER_LONG. That would save _a lot_ on useless small kmalloc()
> calls.

Okay that's clever. We would probably avoid the need for allocations in
the vast vast majority of cases with that approach.

> The whole business of dynamic arrays is about potentially infinite
> number of elements. User of your array doesn't even care about the
> exact length, because it may get changed anytime, right?
> 
> In that case, the comment would sound like:
> 
>   // Zero-size Bitmap request yields a bitmap of an arbitrary
>   // non-zero length.
> 
> [...]
>  
> > The clippy linter emits a warning if you have a `len` method but don't
> > have an `is_empty` method, since Rust containers usually have both.
> > 
> > https://rust-lang.github.io/rust-clippy/master/index.html#len_without_is_empty
> > 
> > But the confusion with "no set bits" seems like a good reason to silence
> > that warning for bitmap.
>  
> So the comment at your link says:
> 
>  It is good custom to have both methods, because for some data structures,
>  asking about the length will be a costly operation, whereas .is_empty()
>  can usually answer in constant time.
> 
> In this case both len() and is_empty() are O(1), but the last one
> is totally misleading.
> 
> You guys would better teach your linter to understand when the len()
> is cheap, so is_empty() is useless.

Heh, I'm not sure I agree with the lint's explanation. But all stdlib
Rust data structures have both `len` and `is_empty` even if computing
the length is O(1). In my eyes, it's just a convention, similar to
calling the constructor "new".

> > > > +    /// Sets bit with index `index`.
> > > > +    ///
> > > > +    /// # Panics
> > > > +    ///
> > > > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > > > +    #[inline]
> > > > +    pub fn set_bit(&mut self, index: usize) {
> > > 
> > > set_bit() is an atomic name, but you wire it to a non-atomic operation.
> > > This is a mess.
> > 
> > Hmm. I do generally agree that we should try to match C names, but I'm
> > unsure about this particular case due to the underscores.
> > 
> > This method takes "&mut self" rather than "&self", which means that the
> > caller must have exclusive access to the bitmap to call this method.
> > Attempting to call it when the bitmap is shared will result in a
> > compilation failure, so it is impossible to call the non-atomic method
> > in cases where you must use the atomic version.
> 
> Does mutual access implies memory barriers? Your code doesn't add
> them. Is rust compiler so smart to realize that you need it?
> 
> I mean the following scenario:
> 
> CPU1                            CPU2
> a.set_bit(1)
>                                 a.test_bit(1) -> 0
> cache_flush()
>                                 a.test_bit(1) -> 1
> 
> If the above is impossible, then yes, your set_bit is atomic.

Yes, if a method is "&mut self" then this case is impossible.

Basically, the way it works is that the only APIs that hand out `&mut`
references to a value must somehow enforce that the access is exclusive.
How it enforces that is up to the API.

So for example, if you have a local variable that you know is not
shared, you can just obtain a `&mut` reference to it. No barriers needed
since it's a local variable that is not shared.

On the other hand, if you have a variable protected by a spinlock, then
the spinlock API will only hand out `&mut` references when the spinlock
is locked. And the borrow-checker enforces that the `&mut` can't be used
after you unlock it again. In this case, the spin_lock / spin_unlock
calls are sufficient barriers to use __set_bit.

And so on for each synchronization method.

Point is, any time you have a `&mut` reference to a value, you know that
it's exclusive, because whichever API created that reference has some
mechanism to ensure that.

> > We could call this method __set_bit, but using underscore prefixes for
> > methods is very very rare in Rust code because prefixing a name with an
> > underscore usually means "do not emit warnings if this thing is unused".
> > For example, when locking a mutex, you might write this:
> > 
> > {
> >     let _lock = my_mutex.lock();
> >     // do stuff ...
> > 
> >     // _lock goes out of scope here, unlocking the mutex
> > }
> > 
> > Here, if you called the variable "lock" you would get an unused variable
> > warning, but prefixing the variable name with an underscore silences
> > that warning.
> 
> But underscored method is not a local underscored variable. It doesn't
> have scope.

If a method isn't public, then Rust will perform a similar check to the
entire compilation unit and emit a warning if it's unused. The
underscore silences that.

Though as Miguel points out, this particular method is public, so the
check is not performed - there might be callers in other compilation
units that this rustc invocation doesn't know about.

> > We can still call the method __set_bit if you think that is best, but
> 
> No I don't. Nobody likes underscored notation for non-atomic bit ops,
> but it's a historical thing.
> 
> > because underscore prefixes usually mean something different in Rust, I
> > wonder if we should use slightly different names in Rust. Thoughts?
> 
> This is a new project, and you may decide to change notation. Just
> please be very specific about it.
> 
> So I'd suggest the following:
> 
> 1. Mirror C interface: __set_bit() and set_bit()
> 2. set_bit_nonatomic() and set_bit()
> 3. set_bit() and set_bit_atomic()
> 
> The last one looks the best to me, except that it just the opposite
> to what people got used to in Linux. If you go with #3, please add
> both atomic and non-atomic set_bit()s in the same patch, together with
> a bunch of comments, so people will be aware.

Solution #3 sounds good to me.

Alice