[PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[PATCH v7 0/5] rust: adds 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.

We include set_bit_atomic and clear_bit_atomic operations. One has
to avoid races with non-atomic operations, which is ensure by the
Rust type system: either callers have shared references &bitmap in
which case the mutations are atomic operations. Or there is a
exclusive reference &mut bitmap, in which case there is no concurrent
access.

This version includes an optimization to represent the bitmap inline,
as suggested by Yury.

We introduce a Rust API that would replace (dbitmap.h) in file id_pool.rs. 
This data structure is tightly coupled to the bitmap API. Includes an example of usage
that requires releasing a spinlock, as expected in Binder driver.

This is v7 of a patch introducing Rust bitmap API [v6]. Thanks
for all the helpful comments, this series has improved significantly
as a result of your work.

Changes v6 --> v7:
- Added separate unit tests in bitmap.rs and benchmark module,
  following the example in find_bit_benchmark.c
- Added discussion about using vendored bitset to commit message.
- Refined warning about naming convention

Changes v5 --> v6:
- Added SAFETY comment for atomic operations.
- Added missing volatile to bitops set_bit and clear_bit bindings.
- Fixed condition on `nbits` to be <= i32::MAX, update SAFETY comments.
- Readability improvements.
- Updated doc comments wording and indentation.

Changes v4 --> v5: (suggested by Yury and Alice)
- rebased on next-20250318
- split MAINTAINERS changes
- no dependencies on [1] and [2] anymore - Viresh,
  please do add a separate section if you want to maintain cpumask.rs
  separately.
- imports atomic and non-atomic variants, introduces a naming convention
  set_bit and set_bit_atomic on the Rust side.
- changed naming and comments. Keeping `new`.
- change dynamic_id_pool to id_pool
- represent bitmap inline when possible
- add some more tests
- add myself to M: line for the Rust abstractions

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 [v6] https://lore.kernel.org/rust-for-linux/20250327161617.117748-1-bqe@google.com/ 

Burak Emir (5):
  rust: add bindings for bitmap.h
  rust: add bindings for bitops.h
  rust: add bitmap API.
  rust: add find_bit_benchmark_rust module.
  rust: add dynamic ID pool abstraction for bitmap

 MAINTAINERS                     |  15 ++
 lib/Kconfig.debug               |  15 +-
 lib/Makefile                    |   1 +
 lib/find_bit_benchmark_rust.rs  | 102 ++++++++
 rust/bindings/bindings_helper.h |   2 +
 rust/helpers/bitmap.c           |   9 +
 rust/helpers/bitops.c           |  23 ++
 rust/helpers/helpers.c          |   2 +
 rust/kernel/bitmap.rs           | 410 ++++++++++++++++++++++++++++++++
 rust/kernel/id_pool.rs          | 201 ++++++++++++++++
 rust/kernel/lib.rs              |   2 +
 11 files changed, 781 insertions(+), 1 deletion(-)
 create mode 100644 lib/find_bit_benchmark_rust.rs
 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/id_pool.rs

-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 1/5] rust: add bindings for bitmap.h

[Burak Emir]

Makes the bitmap_copy_and_extend inline function available to Rust.
Adds F: to existing MAINTAINERS section BITMAP API BINDINGS [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS                     | 1 +
 rust/bindings/bindings_helper.h | 1 +
 rust/helpers/bitmap.c           | 9 +++++++++
 rust/helpers/helpers.c          | 1 +
 4 files changed, 12 insertions(+)
 create mode 100644 rust/helpers/bitmap.c

diff --git a/MAINTAINERS b/MAINTAINERS
index a5584c5020ac..b11eb9ebc53d 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4132,6 +4132,7 @@ 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
 
 BITOPS API
diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
index ab37e1d35c70..b6bf3b039c1b 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/helpers.c b/rust/helpers/helpers.c
index 0aea103c16be..aa0c0c2cdee2 100644
--- a/rust/helpers/helpers.c
+++ b/rust/helpers/helpers.c
@@ -7,6 +7,7 @@
  * Sorted alphabetically.
  */
 
+#include "bitmap.c"
 #include "blk.c"
 #include "bug.c"
 #include "build_assert.c"
-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 2/5] rust: add bindings for bitops.h

[Burak Emir]

Makes atomic set_bit and clear_bit inline functions as well as the
non-atomic variants __set_bit and __clear_bit available to Rust.
Adds a new MAINTAINERS section BITOPS API BINDINGS [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS            |  5 +++++
 rust/helpers/bitops.c  | 23 +++++++++++++++++++++++
 rust/helpers/helpers.c |  1 +
 3 files changed, 29 insertions(+)
 create mode 100644 rust/helpers/bitops.c

diff --git a/MAINTAINERS b/MAINTAINERS
index b11eb9ebc53d..1f162f64eded 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4149,6 +4149,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/helpers/bitops.c b/rust/helpers/bitops.c
new file mode 100644
index 000000000000..1fe9e3b23a39
--- /dev/null
+++ b/rust/helpers/bitops.c
@@ -0,0 +1,23 @@
+// 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);
+}
+
+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 aa0c0c2cdee2..aaf0f735d1c2 100644
--- a/rust/helpers/helpers.c
+++ b/rust/helpers/helpers.c
@@ -8,6 +8,7 @@
  */
 
 #include "bitmap.c"
+#include "bitops.c"
 #include "blk.c"
 #include "bug.c"
 #include "build_assert.c"
-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 3/5] rust: add bitmap API.

[Burak Emir]

Provides an abstraction for C bitmap API and bitops operations.
We follow the C Bitmap API closely in naming and semantics, with
a few differences that take advantage of Rust language facilities
and idioms:

  * not all operations are exposed yet, to avoid dead code. This commit
    includes enough to implement an Android Binder data structure that
    was introduced in commit 15d9da3f818c ("binder: use bitmap for
    faster descriptor lookup"), namely drivers/android/dbitmap.h. This
    is part of upstreaming the Android Binder driver.

  * API uses Option types where appropriate

  * bound checks are used to treat out-of-bounds access as bug
    (hardening). The C operations treat out-of-bounds parameters
    as a default case e.g. "not found" which is safe (avoids UB) but
    may hide bugs.

  * better naming convention to distinguish non-atomic from atomic
    operations: {set,clear}_bit vs {set,clear}_bit_atomic.
    The Rust type system ensures that all non-atomic operations
    require a &mut reference which amounts to exclusive access.
    Using the atomic variants only makes sense when multiple threads
    have a shared reference &bitmap which amounts to the interior
    mutability pattern.

  * optimized to represent the bitmap inline if it would take the space
    of a pointer. This saves allocations which is relevant in the
    Binder use case.

The underlying C bitmap is *not* exposed. This would lose all static
guarantees.

An alternative route of vendoring an existing Rust bitmap package was
considered but suboptimal overall. Reusing the C implementation is
preferable for a basic data structure like bitmaps. It enables Rust
code to be a lot more similar and predictable with respect to C code
that uses the same data structures and enables the use of code that
has been tried-and-tested in the kernel.

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

Adds new MAINTAINERS section BITMAP API [RUST].

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS           |   7 +
 rust/kernel/bitmap.rs | 396 ++++++++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs    |   1 +
 3 files changed, 404 insertions(+)
 create mode 100644 rust/kernel/bitmap.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index 1f162f64eded..7d107dc91390 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4135,6 +4135,13 @@ S:	Maintained
 F:	rust/helpers/bitmap.c
 F:	rust/helpers/cpumask.c
 
+BITMAP API [RUST]
+M:	Alice Ryhl <aliceryhl@google.com>
+M:	Burak Emir <bqe@google.com>
+R:	Yury Norov <yury.norov@gmail.com>
+S:	Maintained
+F:	rust/kernel/bitmap.rs
+
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
 R:	Rasmus Villemoes <linux@rasmusvillemoes.dk>
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
new file mode 100644
index 000000000000..79ddbef2b028
--- /dev/null
+++ b/rust/kernel/bitmap.rs
@@ -0,0 +1,396 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2025 Google LLC.
+
+//! Rust API for bitmap.
+//!
+//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
+
+use crate::alloc::{AllocError, Flags};
+use crate::bindings;
+use core::ptr::NonNull;
+
+/// Holds either a pointer to array of `unsigned long` or a small bitmap.
+#[repr(C)]
+union BitmapRepr {
+    bitmap: usize,
+    ptr: NonNull<usize>,
+}
+
+/// Represents a bitmap.
+///
+/// Wraps underlying C bitmap API.
+///
+/// # Examples
+///
+/// Basic usage
+///
+/// ```
+/// use kernel::alloc::flags::GFP_KERNEL;
+/// use kernel::bitmap::Bitmap;
+///
+/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
+///
+/// assert_eq!(16, b.len());
+/// for i in 0..16 {
+///     if i % 4 == 0 {
+///       b.set_bit(i);
+///     }
+/// }
+/// assert_eq!(Some(0), b.next_bit(0));
+/// assert_eq!(Some(1), b.next_zero_bit(0));
+/// assert_eq!(Some(4), b.next_bit(1));
+/// assert_eq!(Some(5), b.next_zero_bit(4));
+/// assert_eq!(Some(12), b.last_bit());
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// # Invariants
+///
+/// * `nbits` is `<= i32::MAX` and never changes.
+/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a bitmap.
+/// * otherwise, `repr` holds a non-null pointer that was obtained from a
+///   successful call to `bitmap_zalloc` and holds the address of an initialized
+///   array of `unsigned long` that is large enough to hold `nbits` bits.
+pub struct Bitmap {
+    /// Representation of bitmap.
+    repr: BitmapRepr,
+    /// Length of this bitmap. Must be `<= i32::MAX`.
+    nbits: usize,
+}
+
+impl Drop for Bitmap {
+    fn drop(&mut self) {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            return;
+        }
+        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
+        //
+        // INVARIANT: there is no other use of the `self.ptr` after this
+        // call and the value is being dropped so the broken invariant is
+        // not observable on function exit.
+        unsafe { bindings::bitmap_free(self.as_mut_ptr()) };
+    }
+}
+
+impl Bitmap {
+    /// Constructs a new [`Bitmap`].
+    ///
+    /// Fails with [`AllocError`] when the [`Bitmap`] could not be allocated. This
+    /// includes the case when `nbits` is greater than `i32::MAX`.
+    #[inline]
+    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
+        if nbits <= bindings::BITS_PER_LONG as _ {
+            return Ok(Bitmap {
+                repr: BitmapRepr { bitmap: 0 },
+                nbits,
+            });
+        }
+        if nbits > i32::MAX.try_into().unwrap() {
+            return Err(AllocError);
+        }
+        let nbits_u32 = u32::try_from(nbits).unwrap();
+        // SAFETY: `bindings::BITS_PER_LONG < nbits` and `nbits <= i32::MAX`.
+        let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
+        let ptr = NonNull::new(ptr).ok_or(AllocError)?;
+        // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
+        return Ok(Bitmap {
+            repr: BitmapRepr { ptr },
+            nbits,
+        });
+    }
+
+    /// Returns length of this [`Bitmap`].
+    #[inline]
+    pub fn len(&self) -> usize {
+        self.nbits
+    }
+
+    /// Returns a mutable raw pointer to the backing [`Bitmap`].
+    #[inline]
+    fn as_mut_ptr(&mut self) -> *mut usize {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            // SAFETY: Bitmap is represented inline.
+            unsafe { core::ptr::addr_of_mut!(self.repr.bitmap) }
+        } else {
+            // SAFETY: Bitmap is represented as array of `unsigned long`.
+            unsafe { self.repr.ptr.as_mut() }
+        }
+    }
+
+    /// Returns a raw pointer to the backing [`Bitmap`].
+    #[inline]
+    fn as_ptr(&self) -> *const usize {
+        if self.nbits <= bindings::BITS_PER_LONG as _ {
+            // SAFETY: Bitmap is represented inline.
+            unsafe { core::ptr::addr_of!(self.repr.bitmap) }
+        } else {
+            // SAFETY: Bitmap is represented as array of `unsigned long`.
+            unsafe { self.repr.ptr.as_ptr() }
+        }
+    }
+
+    /// Set bit with index `index`.
+    ///
+    /// ATTENTION: `set_bit` is non-atomic, which differs from the naming
+    /// convention in C code. The corresponding C function is `__set_bit`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn set_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: Bit `index` is within bounds.
+        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Set bit with index `index`, atomically.
+    ///
+    /// This is a relaxed atomic operation (no implied memory barriers).
+    ///
+    /// ATTENTION: The naming convention differs from C, where the corresponding
+    /// function is called `set_bit`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn set_bit_atomic(&self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds and there cannot be any data races
+        // because all non-atomic operations require exclusive access through
+        // a &mut reference.
+        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
+    }
+
+    /// Clear `index` bit.
+    ///
+    /// ATTENTION: `clear_bit` is non-atomic, which differs from the naming
+    /// convention in C code. The corresponding C function is `__clear_bit`.
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn clear_bit(&mut self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds.
+        unsafe { bindings::__clear_bit(index as u32, self.as_mut_ptr()) };
+    }
+
+    /// Clear `index` bit, atomically.
+    ///
+    /// This is a relaxed atomic operation (no implied memory barriers).
+    ///
+    /// ATTENTION: The naming convention differs from C, where the corresponding
+    /// function is called `clear_bit`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn clear_bit_atomic(&self, index: usize) {
+        assert!(
+            index < self.nbits,
+            "Bit `index` must be < {}, was {}",
+            self.nbits,
+            index
+        );
+        // SAFETY: `index` is within bounds and there cannot be any data races
+        // because all non-atomic operations require exclusive access through
+        // a &mut reference.
+        unsafe { bindings::clear_bit(index as u32, self.as_ptr() as *mut usize) };
+    }
+
+    /// Copy `src` into this [`Bitmap`] and set any remaining bits to zero.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
+    //
+    /// assert_eq!(None, long_bitmap.last_bit());
+    //
+    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
+    //
+    /// short_bitmap.set_bit(7);
+    /// long_bitmap.copy_and_extend(&short_bitmap);
+    /// assert_eq!(Some(7), long_bitmap.last_bit());
+    ///
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn copy_and_extend(&mut self, src: &Bitmap) {
+        let len = core::cmp::min(src.nbits, self.nbits);
+        // SAFETY: access to `self` and `src` is within bounds.
+        unsafe {
+            bindings::bitmap_copy_and_extend(
+                self.as_mut_ptr(),
+                src.as_ptr(),
+                len as u32,
+                self.nbits as u32,
+            )
+        };
+    }
+
+    /// Finds last set bit.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::bitmap::Bitmap;
+    ///
+    /// let bitmap = Bitmap::new(64, GFP_KERNEL)?;
+    ///
+    /// match bitmap.last_bit() {
+    ///     Some(idx) => {
+    ///         pr_info!("The last bit has index {idx}.\n");
+    ///     }
+    ///     None => {
+    ///         pr_info!("All bits in this bitmap are 0.\n");
+    ///     }
+    /// }
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn last_bit(&self) -> Option<usize> {
+        // SAFETY: access is within bounds.
+        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+
+    /// Finds next set bit, starting from `start`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `start` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn next_bit(&self, start: usize) -> Option<usize> {
+        assert!(
+            start < self.nbits,
+            "`start` must be < {}, was {}",
+            self.nbits,
+            start
+        );
+
+        // SAFETY: access is within bounds.
+        let index = unsafe { bindings::_find_next_bit(self.as_ptr(), self.nbits, start) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+
+    /// Finds next zero bit, starting from `start`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `start` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
+        assert!(
+            start < self.nbits,
+            "`start` must be < {}, was {}",
+            self.nbits,
+            start
+        );
+
+        // SAFETY: access is within bounds.
+        let index = unsafe { bindings::_find_next_zero_bit(self.as_ptr(), self.nbits, start) };
+        if index == self.nbits {
+            None
+        } else {
+            Some(index)
+        }
+    }
+}
+
+use macros::kunit_tests;
+
+#[kunit_tests(rust_kernel_bitmap)]
+mod tests {
+    use super::*;
+    use kernel::alloc::flags::GFP_KERNEL;
+
+    #[test]
+    fn bitmap_new() {
+        let b = Bitmap::new(0, GFP_KERNEL).unwrap();
+        assert_eq!(0, b.len());
+
+        let b = Bitmap::new(3, GFP_KERNEL).unwrap();
+        assert_eq!(3, b.len());
+
+        let b = Bitmap::new(1024, GFP_KERNEL).unwrap();
+        assert_eq!(1024, b.len());
+
+        // Requesting too large values results in [`AllocError`].
+        let b = Bitmap::new(1 << 31, GFP_KERNEL);
+        assert!(b.is_err());
+    }
+
+    #[test]
+    fn bitmap_set_clear_find() {
+        let mut b = Bitmap::new(128, GFP_KERNEL).unwrap();
+
+        // Zero-initialized
+        assert_eq!(None, b.last_bit());
+
+        b.set_bit(17);
+
+        assert_eq!(Some(17), b.next_bit(0));
+        assert_eq!(Some(17), b.last_bit());
+
+        b.set_bit(107);
+
+        assert_eq!(Some(17), b.next_bit(0));
+        assert_eq!(Some(17), b.next_bit(17));
+        assert_eq!(Some(107), b.next_bit(18));
+        assert_eq!(Some(107), b.last_bit());
+
+        b.clear_bit(17);
+
+        assert_eq!(Some(107), b.next_bit(0));
+        assert_eq!(Some(107), b.last_bit());
+    }
+
+    #[test]
+    fn bitmap_copy_and_extend() {
+        let mut long_bitmap = Bitmap::new(256, GFP_KERNEL).unwrap();
+
+        long_bitmap.set_bit(3);
+        long_bitmap.set_bit(200);
+
+        let mut short_bitmap = Bitmap::new(32, GFP_KERNEL).unwrap();
+
+        short_bitmap.set_bit(17);
+
+        long_bitmap.copy_and_extend(&short_bitmap);
+        // The larger bits have been cleared.
+        assert_eq!(Some(17), long_bitmap.next_bit(0));
+        assert_eq!(Some(17), long_bitmap.last_bit());
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index 42ab6cf4053f..94eb150c52c7 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -38,6 +38,7 @@
 pub use ffi;
 
 pub mod alloc;
+pub mod bitmap;
 #[cfg(CONFIG_BLOCK)]
 pub mod block;
 #[doc(hidden)]
-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Burak Emir]

Microbenchmark protected by a config FIND_BIT_BENCHMARK_RUST,
following `find_bit_benchmark.c` but testing the Rust Bitmap API.

We add a fill_random() method protected by the config in order to
maintain the abstraction.

Minor fix to the documentation of the corresponding C config
FIND_BIT_BENCHMARK, it was mentioning the wrong module name.

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS                     |   1 +
 lib/Kconfig.debug               |  15 ++++-
 lib/Makefile                    |   1 +
 lib/find_bit_benchmark_rust.rs  | 102 ++++++++++++++++++++++++++++++++
 rust/bindings/bindings_helper.h |   1 +
 rust/kernel/bitmap.rs           |  14 +++++
 6 files changed, 133 insertions(+), 1 deletion(-)
 create mode 100644 lib/find_bit_benchmark_rust.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index 7d107dc91390..d448b73c5934 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4140,6 +4140,7 @@ M:	Alice Ryhl <aliceryhl@google.com>
 M:	Burak Emir <bqe@google.com>
 R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
+F:	lib/find_bit_benchmark_rust.rs
 F:	rust/kernel/bitmap.rs
 
 BITOPS API
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index f9051ab610d5..c1d4fc4a5f8f 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2600,11 +2600,24 @@ config TEST_BPF
 config FIND_BIT_BENCHMARK
 	tristate "Test find_bit functions"
 	help
-	  This builds the "test_find_bit" module that measure find_*_bit()
+	  This builds the "find_bit_benchmark" module that measure find_*_bit()
 	  functions performance.
 
 	  If unsure, say N.
 
+config FIND_BIT_BENCHMARK_RUST
+	tristate "Test find_bit functions in Rust"
+	help
+	  This builds the "find_bit_benchmark_rust" module. It is a micro
+          benchmark that measures the performance of Rust functions that
+          correspond to the find_*_bit() operations in C. It follows the
+          FIND_BIT_BENCHMARK closely but will in general not yield same
+          numbers due to extra bounds checks and overhead of foreign
+          function calls.
+
+	  If unsure, say N.
+
+
 config TEST_FIRMWARE
 	tristate "Test firmware loading via userspace interface"
 	depends on FW_LOADER
diff --git a/lib/Makefile b/lib/Makefile
index f07b24ce1b3f..99e49a8f5bf8 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -62,6 +62,7 @@ obj-y += hexdump.o
 obj-$(CONFIG_TEST_HEXDUMP) += test_hexdump.o
 obj-y += kstrtox.o
 obj-$(CONFIG_FIND_BIT_BENCHMARK) += find_bit_benchmark.o
+obj-$(CONFIG_FIND_BIT_BENCHMARK_RUST) += find_bit_benchmark_rust.o
 obj-$(CONFIG_TEST_BPF) += test_bpf.o
 test_dhry-objs := dhry_1.o dhry_2.o dhry_run.o
 obj-$(CONFIG_TEST_DHRY) += test_dhry.o
diff --git a/lib/find_bit_benchmark_rust.rs b/lib/find_bit_benchmark_rust.rs
new file mode 100644
index 000000000000..9f4661baf70b
--- /dev/null
+++ b/lib/find_bit_benchmark_rust.rs
@@ -0,0 +1,102 @@
+// SPDX-License-Identifier: GPL-2.0
+//! Benchmark for find_bit-like methods in Bitmap Rust API.
+
+use kernel::alloc::flags::GFP_KERNEL;
+use kernel::bindings;
+use kernel::bitmap::Bitmap;
+use kernel::error::{code, Result};
+use kernel::pr_err;
+use kernel::prelude::module;
+use kernel::time::Ktime;
+use kernel::ThisModule;
+
+const BITMAP_LEN: usize = 4096 * 8 * 10;
+// Reciprocal of the fraction of bits that are set in sparse bitmap.
+const SPARSENESS: usize = 500;
+
+/// Test module that benchmarks performance of traversing bitmaps.
+struct FindBitBenchmarkModule();
+
+fn test_find_next_bit(bitmap: &Bitmap) {
+    let mut time = Ktime::ktime_get();
+    let mut cnt = 0;
+    let mut i = 0;
+
+    loop {
+        cnt += 1;
+        if let Some(index) = bitmap.next_bit(i) {
+            i = index + 1;
+            if i == BITMAP_LEN {
+                break;
+            }
+        } else {
+            break;
+        }
+    }
+
+    time = Ktime::ktime_get() - time;
+    pr_err!("find_next_bit: {} ns, {} iterations\n", time.to_ns(), cnt);
+}
+
+fn test_find_next_zero_bit(bitmap: &Bitmap) {
+    let mut time = Ktime::ktime_get();
+    let mut cnt = 0;
+    let mut i = 0;
+    loop {
+        cnt += 1;
+        if let Some(index) = bitmap.next_zero_bit(i) {
+            i = index + 1;
+            if i == BITMAP_LEN {
+                break;
+            }
+        } else {
+            break;
+        }
+    }
+    time = Ktime::ktime_get() - time;
+    pr_err!(
+        "find_next_zero_bit: {} ns, {} iterations\n",
+        time.to_ns(),
+        cnt
+    );
+}
+
+fn find_bit_test() {
+    pr_err!("Start testing find_bit() Rust with random-filled bitmap\n");
+
+    let mut bitmap = Bitmap::new(BITMAP_LEN, GFP_KERNEL).expect("alloc bitmap failed");
+    bitmap.fill_random();
+
+    test_find_next_bit(&bitmap);
+    test_find_next_zero_bit(&bitmap);
+
+    pr_err!("Start testing find_bit() Rust with sparse bitmap\n");
+
+    let mut bitmap = Bitmap::new(BITMAP_LEN, GFP_KERNEL).expect("alloc sparse bitmap failed");
+    let nbits = BITMAP_LEN / SPARSENESS;
+    for _i in 0..nbits {
+        // SAFETY: BITMAP_LEN fits in 32 bits.
+        let bit: usize =
+            unsafe { bindings::__get_random_u32_below(BITMAP_LEN.try_into().unwrap()) as _ };
+        bitmap.set_bit(bit);
+    }
+
+    test_find_next_bit(&bitmap);
+    test_find_next_zero_bit(&bitmap);
+}
+
+impl kernel::Module for FindBitBenchmarkModule {
+    fn init(_module: &'static ThisModule) -> Result<Self> {
+        find_bit_test();
+        // Return error so test module can be inserted again without rmmod.
+        Err(code::EINVAL)
+    }
+}
+
+module! {
+    type: FindBitBenchmarkModule,
+    name: "find_bit_benchmark_rust_module",
+    authors: ["Rust for Linux Contributors"],
+    description: "Module with benchmark for bitmap code!",
+    license: "GPL v2",
+}
diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
index b6bf3b039c1b..f6ca7f1dd08b 100644
--- a/rust/bindings/bindings_helper.h
+++ b/rust/bindings/bindings_helper.h
@@ -31,6 +31,7 @@
 #include <linux/platform_device.h>
 #include <linux/poll.h>
 #include <linux/property.h>
+#include <linux/random.h>
 #include <linux/refcount.h>
 #include <linux/sched.h>
 #include <linux/security.h>
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index 79ddbef2b028..5d2f6978ee6e 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -106,6 +106,20 @@ pub fn len(&self) -> usize {
         self.nbits
     }
 
+    /// Fills this `Bitmap` with random bits.
+    #[cfg(CONFIG_FIND_BIT_BENCHMARK_RUST)]
+    pub fn fill_random(&mut self) {
+        // SAFETY: `self.as_mut_ptr` points to either an array of the
+        // appropriate length or one usize.
+        unsafe {
+            bindings::get_random_bytes(
+                self.as_mut_ptr() as *mut ffi::c_void,
+                usize::div_ceil(self.nbits, bindings::BITS_PER_LONG as usize)
+                    * bindings::BITS_PER_LONG as usize,
+            );
+        }
+    }
+
     /// Returns a mutable raw pointer to the backing [`Bitmap`].
     #[inline]
     fn as_mut_ptr(&mut self) -> *mut usize {
-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v7 5/5] rust: add dynamic ID pool abstraction for bitmap

[Burak Emir]

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

Like drivers/android/dbitmap.h, the ID pool abstraction lets
clients acquire and release IDs. The implementation uses a bitmap to
know what IDs are in use, and gives clients fine-grained control over
the time of allocation. This fine-grained control is needed in the
Android Binder. We provide an example that release a spinlock for
allocation and unit tests (rustdoc examples).

The implementation is not aware that the underlying Bitmap abstraction
handles lengths below BITS_PER_LONG without allocation.

Suggested-by: Alice Ryhl <aliceryhl@google.com>
Suggested-by: Yury Norov <yury.norov@gmail.com>
Signed-off-by: Burak Emir <bqe@google.com>
---
 MAINTAINERS            |   1 +
 rust/kernel/id_pool.rs | 201 +++++++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs     |   1 +
 3 files changed, 203 insertions(+)
 create mode 100644 rust/kernel/id_pool.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index d448b73c5934..161281251108 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4142,6 +4142,7 @@ R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
 F:	lib/find_bit_benchmark_rust.rs
 F:	rust/kernel/bitmap.rs
+F:	rust/kernel/id_pool.rs
 
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
new file mode 100644
index 000000000000..8f07526bb580
--- /dev/null
+++ b/rust/kernel/id_pool.rs
@@ -0,0 +1,201 @@
+// 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::id_pool::IdPool;
+///
+/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
+/// for i in 0..64 {
+///   assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
+/// }
+///
+/// pool.release_id(23);
+/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
+///
+/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
+/// let resizer = pool.grow_alloc().alloc(GFP_KERNEL)?;
+/// pool.grow(resizer);
+///
+/// assert_eq!(pool.acquire_next_id(0), Some(64));
+/// # Ok::<(), Error>(())
+/// ```
+///
+/// Releasing spinlock to grow the pool
+///
+/// ```no_run
+/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+/// use kernel::sync::{new_spinlock, SpinLock};
+/// use kernel::id_pool::IdPool;
+///
+/// fn get_id_maybe_alloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
+///   let mut pool = guarded_pool.lock();
+///   loop {
+///     match pool.acquire_next_id(0) {
+///       Some(index) => return Ok(index),
+///       None => {
+///         let alloc_request = pool.grow_alloc();
+///         drop(pool);
+///         let resizer = alloc_request.alloc(GFP_KERNEL)?;
+///         pool = guarded_pool.lock();
+///         pool.grow(resizer)
+///       }
+///     }
+///   }
+/// }
+/// ```
+pub struct IdPool {
+    map: Bitmap,
+}
+
+/// Returned when the `IdPool` should change size.
+pub struct AllocRequest {
+    nbits: usize,
+}
+
+/// Contains an allocated `Bitmap` for resizing `IdPool`.
+pub struct PoolResizer {
+    new: Bitmap,
+}
+
+impl AllocRequest {
+    /// Allocates a new `Bitmap` for `IdPool`.
+    pub fn alloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
+        let new = Bitmap::new(self.nbits, flags)?;
+        Ok(PoolResizer { new })
+    }
+}
+
+impl IdPool {
+    /// Constructs a new `[IdPool]`.
+    #[inline]
+    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
+        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 [`IdPool`] can be shrunk, [`None`] otherwise.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
+    /// use kernel::id_pool::{AllocRequest, IdPool};
+    ///
+    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
+    /// let alloc_request = pool.shrink_alloc().ok_or(AllocError)?;
+    /// let resizer = alloc_request.alloc(GFP_KERNEL)?;
+    /// pool.shrink(resizer);
+    /// assert_eq!(pool.len(), kernel::bindings::BITS_PER_LONG as usize);
+    /// # Ok::<(), AllocError>(())
+    /// ```
+    #[inline]
+    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
+        let len = self.map.len();
+        if len <= bindings::BITS_PER_LONG as usize {
+            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.last_bit() {
+            Some(bit) => {
+                if bit < (len >> 2) {
+                    Some(AllocRequest { nbits: len >> 1 })
+                } else {
+                    None
+                }
+            }
+            None => Some(AllocRequest {
+                nbits: bindings::BITS_PER_LONG as usize,
+            }),
+        }
+    }
+
+    /// 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_and_extend(&self.map);
+                self.map = resizer.new;
+                return;
+            }
+        }
+    }
+
+    /// Returns an `AllocRequest` for growing this `IdPool`.
+    #[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_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.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 94eb150c52c7..4c6b45dcad04 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -54,6 +54,7 @@
 #[cfg(CONFIG_RUST_FW_LOADER_ABSTRACTIONS)]
 pub mod firmware;
 pub mod fs;
+pub mod id_pool;
 pub mod init;
 pub mod io;
 pub mod ioctl;
-- 
2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

I received it twice - with timestamps 1:36 and 1:43. Assuming they are
identical, and ignoring the former.

On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> 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.
> 
> We include set_bit_atomic and clear_bit_atomic operations. One has
> to avoid races with non-atomic operations, which is ensure by the
> Rust type system: either callers have shared references &bitmap in
> which case the mutations are atomic operations. Or there is a
> exclusive reference &mut bitmap, in which case there is no concurrent
> access.

It's not about shared references only. One can take a mutable
reference, and still may have a race:

CPU1                            CPU2

take mut ref
bitmap.set() // non-atomic
put mut ref     
                                take mut ref
                                bitmap.test() // read as 0
data propagated to memory       
                                bitmap.test() // read as 1

To make this scenario impossible, either put or take mut ref
should imply global cache flush, because bitmap array is not
an internal data for the Bitmap class (only the pointer is).

I already asked you to point me to the specification that states that
taking mutable reference implies flushing all the caches to the point
of coherency, but you didn't share it. And I doubt that compiler does
it, for the performance considerations.

Thanks,
Yury

> This version includes an optimization to represent the bitmap inline,
> as suggested by Yury.
> 
> We introduce a Rust API that would replace (dbitmap.h) in file id_pool.rs. 
> This data structure is tightly coupled to the bitmap API. Includes an example of usage
> that requires releasing a spinlock, as expected in Binder driver.
> 
> This is v7 of a patch introducing Rust bitmap API [v6]. Thanks
> for all the helpful comments, this series has improved significantly
> as a result of your work.
> 
> Changes v6 --> v7:
> - Added separate unit tests in bitmap.rs and benchmark module,
>   following the example in find_bit_benchmark.c
> - Added discussion about using vendored bitset to commit message.
> - Refined warning about naming convention
> 
> Changes v5 --> v6:
> - Added SAFETY comment for atomic operations.
> - Added missing volatile to bitops set_bit and clear_bit bindings.
> - Fixed condition on `nbits` to be <= i32::MAX, update SAFETY comments.
> - Readability improvements.
> - Updated doc comments wording and indentation.
> 
> Changes v4 --> v5: (suggested by Yury and Alice)
> - rebased on next-20250318
> - split MAINTAINERS changes
> - no dependencies on [1] and [2] anymore - Viresh,
>   please do add a separate section if you want to maintain cpumask.rs
>   separately.
> - imports atomic and non-atomic variants, introduces a naming convention
>   set_bit and set_bit_atomic on the Rust side.
> - changed naming and comments. Keeping `new`.
> - change dynamic_id_pool to id_pool
> - represent bitmap inline when possible
> - add some more tests
> - add myself to M: line for the Rust abstractions
> 
> 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 [v6] https://lore.kernel.org/rust-for-linux/20250327161617.117748-1-bqe@google.com/ 
> 
> Burak Emir (5):
>   rust: add bindings for bitmap.h
>   rust: add bindings for bitops.h
>   rust: add bitmap API.
>   rust: add find_bit_benchmark_rust module.
>   rust: add dynamic ID pool abstraction for bitmap
> 
>  MAINTAINERS                     |  15 ++
>  lib/Kconfig.debug               |  15 +-
>  lib/Makefile                    |   1 +
>  lib/find_bit_benchmark_rust.rs  | 102 ++++++++
>  rust/bindings/bindings_helper.h |   2 +
>  rust/helpers/bitmap.c           |   9 +
>  rust/helpers/bitops.c           |  23 ++
>  rust/helpers/helpers.c          |   2 +
>  rust/kernel/bitmap.rs           | 410 ++++++++++++++++++++++++++++++++
>  rust/kernel/id_pool.rs          | 201 ++++++++++++++++
>  rust/kernel/lib.rs              |   2 +
>  11 files changed, 781 insertions(+), 1 deletion(-)
>  create mode 100644 lib/find_bit_benchmark_rust.rs
>  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/id_pool.rs
> 
> -- 
> 2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 1/5] rust: add bindings for bitmap.h

[Yury Norov]

On Wed, Apr 23, 2025 at 01:43:33PM +0000, Burak Emir wrote:
> Makes the bitmap_copy_and_extend inline function available to Rust.
> Adds F: to existing MAINTAINERS section BITMAP API BINDINGS [RUST].
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Suggested-by: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Burak Emir <bqe@google.com>

Not sure I suggested it, but whatever.

Acked-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>

> ---
>  MAINTAINERS                     | 1 +
>  rust/bindings/bindings_helper.h | 1 +
>  rust/helpers/bitmap.c           | 9 +++++++++
>  rust/helpers/helpers.c          | 1 +
>  4 files changed, 12 insertions(+)
>  create mode 100644 rust/helpers/bitmap.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index a5584c5020ac..b11eb9ebc53d 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4132,6 +4132,7 @@ 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
>  
>  BITOPS API
> diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
> index ab37e1d35c70..b6bf3b039c1b 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/helpers.c b/rust/helpers/helpers.c
> index 0aea103c16be..aa0c0c2cdee2 100644
> --- a/rust/helpers/helpers.c
> +++ b/rust/helpers/helpers.c
> @@ -7,6 +7,7 @@
>   * Sorted alphabetically.
>   */
>  
> +#include "bitmap.c"
>  #include "blk.c"
>  #include "bug.c"
>  #include "build_assert.c"
> -- 
> 2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 2/5] rust: add bindings for bitops.h

[Yury Norov]

On Wed, Apr 23, 2025 at 01:43:34PM +0000, Burak Emir wrote:
> Makes atomic set_bit and clear_bit inline functions as well as the
> non-atomic variants __set_bit and __clear_bit available to Rust.
> Adds a new MAINTAINERS section BITOPS API BINDINGS [RUST].
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Suggested-by: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Burak Emir <bqe@google.com>

Acked-by: Yury Norov [NVIDIA] <yury.norov@gmail.com>

> ---
>  MAINTAINERS            |  5 +++++
>  rust/helpers/bitops.c  | 23 +++++++++++++++++++++++
>  rust/helpers/helpers.c |  1 +
>  3 files changed, 29 insertions(+)
>  create mode 100644 rust/helpers/bitops.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index b11eb9ebc53d..1f162f64eded 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4149,6 +4149,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/helpers/bitops.c b/rust/helpers/bitops.c
> new file mode 100644
> index 000000000000..1fe9e3b23a39
> --- /dev/null
> +++ b/rust/helpers/bitops.c
> @@ -0,0 +1,23 @@
> +// 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);
> +}
> +
> +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 aa0c0c2cdee2..aaf0f735d1c2 100644
> --- a/rust/helpers/helpers.c
> +++ b/rust/helpers/helpers.c
> @@ -8,6 +8,7 @@
>   */
>  
>  #include "bitmap.c"
> +#include "bitops.c"
>  #include "blk.c"
>  #include "bug.c"
>  #include "build_assert.c"
> -- 
> 2.49.0.805.g082f7c87e0-goog

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Alice Ryhl]

On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> identical, and ignoring the former.
>
> On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > 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.
> >
> > We include set_bit_atomic and clear_bit_atomic operations. One has
> > to avoid races with non-atomic operations, which is ensure by the
> > Rust type system: either callers have shared references &bitmap in
> > which case the mutations are atomic operations. Or there is a
> > exclusive reference &mut bitmap, in which case there is no concurrent
> > access.
>
> It's not about shared references only. One can take a mutable
> reference, and still may have a race:
>
> CPU1                            CPU2
>
> take mut ref
> bitmap.set() // non-atomic
> put mut ref
>                                 take mut ref
>                                 bitmap.test() // read as 0
> data propagated to memory
>                                 bitmap.test() // read as 1
>
> To make this scenario impossible, either put or take mut ref
> should imply global cache flush, because bitmap array is not
> an internal data for the Bitmap class (only the pointer is).
>
> I already asked you to point me to the specification that states that
> taking mutable reference implies flushing all the caches to the point
> of coherency, but you didn't share it. And I doubt that compiler does
> it, for the performance considerations.

The flushing of caches and so on *is* implied. It doesn't happen every
time you take a mutable reference, but for you to be able to take a
mut ref on CPU2 after releasing it on CPU1, there must be a flush
somewhere in between.

I can try to find docs for it ...

Alice

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > identical, and ignoring the former.
> >
> > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > 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.
> > >
> > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > to avoid races with non-atomic operations, which is ensure by the
> > > Rust type system: either callers have shared references &bitmap in
> > > which case the mutations are atomic operations. Or there is a
> > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > access.
> >
> > It's not about shared references only. One can take a mutable
> > reference, and still may have a race:
> >
> > CPU1                            CPU2
> >
> > take mut ref
> > bitmap.set() // non-atomic
> > put mut ref
> >                                 take mut ref
> >                                 bitmap.test() // read as 0
> > data propagated to memory
> >                                 bitmap.test() // read as 1
> >
> > To make this scenario impossible, either put or take mut ref
> > should imply global cache flush, because bitmap array is not
> > an internal data for the Bitmap class (only the pointer is).
> >
> > I already asked you to point me to the specification that states that
> > taking mutable reference implies flushing all the caches to the point
> > of coherency, but you didn't share it. And I doubt that compiler does
> > it, for the performance considerations.
> 
> The flushing of caches and so on *is* implied. It doesn't happen every
> time you take a mutable reference, but for you to be able to take a
> mut ref on CPU2 after releasing it on CPU1, there must be a flush
> somewhere in between.
> 

Yeah, and it's not just "flushing of caches", it's making CPU1's memory
operations on the object pointed by "mut ref" observable to CPU2. If
CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
CPU1 and CPU2 sync with a store-release+load-acquire, the
RELEASE-ACQUIRE ordering guarantees that as well.

Regards,
Boqun

> I can try to find docs for it ...
> 
> Alice

Re: [PATCH v7 3/5] rust: add bitmap API.

[Yury Norov]

On Wed, Apr 23, 2025 at 01:43:35PM +0000, Burak Emir wrote:
> 
> Provides an abstraction for C bitmap API and bitops operations.
> We follow the C Bitmap API closely in naming and semantics, with
> a few differences that take advantage of Rust language facilities
> and idioms:
> 
>   * not all operations are exposed yet, to avoid dead code. This commit
>     includes enough to implement an Android Binder data structure that
>     was introduced in commit 15d9da3f818c ("binder: use bitmap for
>     faster descriptor lookup"), namely drivers/android/dbitmap.h. This
>     is part of upstreaming the Android Binder driver.
> 
>   * API uses Option types where appropriate
> 
>   * bound checks are used to treat out-of-bounds access as bug
>     (hardening). The C operations treat out-of-bounds parameters
>     as a default case e.g. "not found" which is safe (avoids UB) but
>     may hide bugs.

Few paragraphs later you say:

> It enables Rust
> code to be a lot more similar and predictable with respect to C code

If you want to make Rust similar to C (which is good), you need to
make all that Panic'ing stuff configurable, right?

This is what I suggested originally, and this is the right way to go,
to me.

There was a long discussion few years ago regarding BUG_ON()s in the
kernel, and the bottomline for it is simple: the kernel has many nice
isolating and self-debugging features that help to resolve (hopefully)
non-fatal errors like out-of-bond access, so we should let it try.

Just halting the kernel helps little, particularly it prevents from
collecting syslogs and other debugging info. You can check git history
and see how many BUG()s were demoted to WARN()s, or simply dropped.

So, this is again my suggestion: it's OK to have a hardening feature,
but the panic should be configurable for the reasons:
 - robustness;
 - compatibility;
 - debugability.

To me, this should end up with something like:

  fn bitmap_assert(bool, msg) 
  {
  #if CONFIG_RUST_HARDENING_PANIC && CONFIG_RUST_BITMAP_HARDENING
        assert(bool, msg)
  #elif CONFIG_RUST_BITMAP_HARDENING
        if (!bool)
                pr_err(msg)
  #else
        // do nothing; for the best performance.
  #endif
  }

This doesn't look difficult anyhow right? But if you find it
impractical, you can just replace the panic with printing an error.

After all, this # Panic simply breaks your own coding rules:

  Please note that panicking should be very rare and used only with a good
  reason. In almost all cases, a fallible approach should be used, typically
  returning a ``Result``.

>   * better naming convention to distinguish non-atomic from atomic
>     operations: {set,clear}_bit vs {set,clear}_bit_atomic.
>     The Rust type system ensures that all non-atomic operations
>     require a &mut reference which amounts to exclusive access.
>     Using the atomic variants only makes sense when multiple threads
>     have a shared reference &bitmap which amounts to the interior
>     mutability pattern.
> 
>   * optimized to represent the bitmap inline if it would take the space
>     of a pointer. This saves allocations which is relevant in the
>     Binder use case.
> 
> The underlying C bitmap is *not* exposed. This would lose all static
> guarantees.
> 
> An alternative route of vendoring an existing Rust bitmap package was
> considered but suboptimal overall. Reusing the C implementation is
> preferable for a basic data structure like bitmaps. It enables Rust
> code to be a lot more similar and predictable with respect to C code
> that uses the same data structures and enables the use of code that
> has been tried-and-tested in the kernel.
> 
> We use the `usize` type for sizes and indices into the bitmap,
> because Rust generally always uses that type for indices and lengths
> and it will be more convenient if the API accepts that type. This means
> that we need to perform some casts to/from u32 and usize, since the C
> headers use unsigned int instead of size_t/unsigned long for these
> numbers in some places.
> 
> Adds new MAINTAINERS section BITMAP API [RUST].
> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Suggested-by: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Burak Emir <bqe@google.com>
> ---
>  MAINTAINERS           |   7 +
>  rust/kernel/bitmap.rs | 396 ++++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs    |   1 +
>  3 files changed, 404 insertions(+)
>  create mode 100644 rust/kernel/bitmap.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 1f162f64eded..7d107dc91390 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4135,6 +4135,13 @@ S:	Maintained
>  F:	rust/helpers/bitmap.c
>  F:	rust/helpers/cpumask.c
>  
> +BITMAP API [RUST]
> +M:	Alice Ryhl <aliceryhl@google.com>
> +M:	Burak Emir <bqe@google.com>
> +R:	Yury Norov <yury.norov@gmail.com>
> +S:	Maintained
> +F:	rust/kernel/bitmap.rs
> +
>  BITOPS API
>  M:	Yury Norov <yury.norov@gmail.com>
>  R:	Rasmus Villemoes <linux@rasmusvillemoes.dk>
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> new file mode 100644
> index 000000000000..79ddbef2b028
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,396 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +// Copyright (C) 2025 Google LLC.
> +
> +//! Rust API for bitmap.
> +//!
> +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
> +
> +use crate::alloc::{AllocError, Flags};
> +use crate::bindings;
> +use core::ptr::NonNull;
> +
> +/// Holds either a pointer to array of `unsigned long` or a small bitmap.
> +#[repr(C)]
> +union BitmapRepr {
> +    bitmap: usize,
> +    ptr: NonNull<usize>,
> +}
> +
> +    pub fn last_bit(&self) -> Option<usize> {

[...]

> +        // SAFETY: access is within bounds.
> +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> +        if index == self.nbits {

Here and everywhere, can you please:

        if index >= self.nbits {

I know that bitmap documentation says that index would be exactly
nbits, but really it was a bad decision. If one day I'll find a safe
way to relax this to >=, your code will stay untouched.

Thanks,
Yury

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Yury Norov]

Thanks!

On Wed, Apr 23, 2025 at 01:43:36PM +0000, Burak Emir wrote:
> Microbenchmark protected by a config FIND_BIT_BENCHMARK_RUST,
> following `find_bit_benchmark.c` but testing the Rust Bitmap API.

So? Can you show your numbers?

Can you print the existing C test output back to back with the new one?
Can you also ask 0-day folks to enable your test in their rust config?
 
> We add a fill_random() method protected by the config in order to
> maintain the abstraction.
> 
> Minor fix to the documentation of the corresponding C config
> FIND_BIT_BENCHMARK, it was mentioning the wrong module name.

Indeed. Can you make it a separate patch, please?
  
Thanks,
Yury

> 
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Suggested-by: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Burak Emir <bqe@google.com>

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > identical, and ignoring the former.
> >
> > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > 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.
> > >
> > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > to avoid races with non-atomic operations, which is ensure by the
> > > Rust type system: either callers have shared references &bitmap in
> > > which case the mutations are atomic operations. Or there is a
> > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > access.
> >
> > It's not about shared references only. One can take a mutable
> > reference, and still may have a race:
> >
> > CPU1                            CPU2
> >
> > take mut ref
> > bitmap.set() // non-atomic
> > put mut ref
> >                                 take mut ref
> >                                 bitmap.test() // read as 0
> > data propagated to memory
> >                                 bitmap.test() // read as 1
> >
> > To make this scenario impossible, either put or take mut ref
> > should imply global cache flush, because bitmap array is not
> > an internal data for the Bitmap class (only the pointer is).
> >
> > I already asked you to point me to the specification that states that
> > taking mutable reference implies flushing all the caches to the point
> > of coherency, but you didn't share it. And I doubt that compiler does
> > it, for the performance considerations.
> 
> The flushing of caches and so on *is* implied. It doesn't happen every
> time you take a mutable reference, but for you to be able to take a
> mut ref on CPU2 after releasing it on CPU1, there must be a flush
> somewhere in between.

OK, that makes sense.
 
> I can try to find docs for it ...

Yes please, that would help a lot.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > >
> > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > identical, and ignoring the former.
> > >
> > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > 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.
> > > >
> > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > to avoid races with non-atomic operations, which is ensure by the
> > > > Rust type system: either callers have shared references &bitmap in
> > > > which case the mutations are atomic operations. Or there is a
> > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > access.
> > >
> > > It's not about shared references only. One can take a mutable
> > > reference, and still may have a race:
> > >
> > > CPU1                            CPU2
> > >
> > > take mut ref
> > > bitmap.set() // non-atomic
> > > put mut ref
> > >                                 take mut ref
> > >                                 bitmap.test() // read as 0
> > > data propagated to memory
> > >                                 bitmap.test() // read as 1
> > >
> > > To make this scenario impossible, either put or take mut ref
> > > should imply global cache flush, because bitmap array is not
> > > an internal data for the Bitmap class (only the pointer is).
> > >
> > > I already asked you to point me to the specification that states that
> > > taking mutable reference implies flushing all the caches to the point
> > > of coherency, but you didn't share it. And I doubt that compiler does
> > > it, for the performance considerations.
> > 
> > The flushing of caches and so on *is* implied. It doesn't happen every
> > time you take a mutable reference, but for you to be able to take a
> > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > somewhere in between.
> > 
> 
> Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> operations on the object pointed by "mut ref" observable to CPU2. If
> CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> CPU1 and CPU2 sync with a store-release+load-acquire, the
> RELEASE-ACQUIRE ordering guarantees that as well.

Not sure what you mean. Atomic set_bit() and clear() bit are often
implemented in asm, and there's no acquire-release semantic.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 01:11:21PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > >
> > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > identical, and ignoring the former.
> > > >
> > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > 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.
> > > > >
> > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > Rust type system: either callers have shared references &bitmap in
> > > > > which case the mutations are atomic operations. Or there is a
> > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > access.
> > > >
> > > > It's not about shared references only. One can take a mutable
> > > > reference, and still may have a race:
> > > >
> > > > CPU1                            CPU2
> > > >
> > > > take mut ref
> > > > bitmap.set() // non-atomic
> > > > put mut ref
> > > >                                 take mut ref
> > > >                                 bitmap.test() // read as 0
> > > > data propagated to memory
> > > >                                 bitmap.test() // read as 1
> > > >
> > > > To make this scenario impossible, either put or take mut ref
> > > > should imply global cache flush, because bitmap array is not
> > > > an internal data for the Bitmap class (only the pointer is).
> > > >
> > > > I already asked you to point me to the specification that states that
> > > > taking mutable reference implies flushing all the caches to the point
> > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > it, for the performance considerations.
> > > 
> > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > time you take a mutable reference, but for you to be able to take a
> > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > somewhere in between.
> > > 
> > 
> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > RELEASE-ACQUIRE ordering guarantees that as well.
> 
> Not sure what you mean. Atomic set_bit() and clear() bit are often
> implemented in asm, and there's no acquire-release semantic.
> 

Well, that's because they are already atomic, therefore no need to
synchronize. Plus if you were to use set_bit() and test_bit() in your
example above, the test_bit() on CPU2 could reads 0, right? I.e. it's
a total different scenario. That is, if you don't synchronize the
operations between two CPUs, you don't get a guarantee of the
observation ordering.

Back the the non-atomic version, taking a very simple example in C,
considering you have:

	struct foo {
		spinlock_t lock;
		long *bitmap;
	}

if you only use non-atomic version i.e. __set_bit() and
__test_bit(), you will need to use lock to synchronize them:

	CPU1			CPU2
	====			====
	spin_lock(&foo->lock);
	__set_bit(foo->bitmap, ...);
	spin_unlock(&foo->lock);
				spin_lock(&foo->lock);
				__test_bit(foo->bitmap, ...);
				// ^ read as 1, because of the lock
				// synchronizes these operations.
				spin_unlock(&foo->lock);

Now if we move to Rust, we will have:

	type Foo = SpinLock<Bitmap>;

and
	CPU1			CPU2
	====
	let foo: &Foo = ...;

	let bitmap: Guard<Bitmap> = foo.lock();

	bitmap.set_bit(); // Guard impls DerefMut

	// lock dropped
				let foo: &Foo = ...;

				let bitmap: Guard<Bitmap> = foo.lock();

				bitmap.test_bit(); // read as 1, same
						   // because of the
						   // lock
						   // synchronization.

So there is nothing different between Rust and C code in this case,
except because in the Rust API, we define that Bitmap::set_bit() and
Bitmap::test_bit() have to take a mutable references, therefore the lock
or some other synchronization has to exist to provide the `&mut Bitmap`,
otherwise you cannot call these functions.

Regards,
Boqun

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > >
> > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > identical, and ignoring the former.
> > > >
> > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > 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.
> > > > >
> > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > Rust type system: either callers have shared references &bitmap in
> > > > > which case the mutations are atomic operations. Or there is a
> > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > access.
> > > >
> > > > It's not about shared references only. One can take a mutable
> > > > reference, and still may have a race:
> > > >
> > > > CPU1                            CPU2
> > > >
> > > > take mut ref
> > > > bitmap.set() // non-atomic
> > > > put mut ref
> > > >                                 take mut ref
> > > >                                 bitmap.test() // read as 0
> > > > data propagated to memory
> > > >                                 bitmap.test() // read as 1
> > > >
> > > > To make this scenario impossible, either put or take mut ref
> > > > should imply global cache flush, because bitmap array is not
> > > > an internal data for the Bitmap class (only the pointer is).
> > > >
> > > > I already asked you to point me to the specification that states that
> > > > taking mutable reference implies flushing all the caches to the point
> > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > it, for the performance considerations.
> > > 
> > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > time you take a mutable reference, but for you to be able to take a
> > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > somewhere in between.
> > > 
> > 
> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > RELEASE-ACQUIRE ordering guarantees that as well.
> 
> Not sure what you mean. Atomic set_bit() and clear() bit are often
> implemented in asm, and there's no acquire-release semantic.

Sorry, hit 'send' preliminary.

> > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > operations on the object pointed by "mut ref" observable to CPU2. If
> > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 

The problem here is that the object pointed by the 'mut ref' is the
rust class Bitmap. The class itself allocates an array, which is used
as an actual storage. The Rust class and C array will likely not share
cache lines.

The pointer is returned from a C call bitmap_zalloc(), so I don't
think it's possible for Rust compiler to realize that the number
stored in Bitmap is a pointer to data of certain size, and that it
should be flushed at "mut ref" put... That's why I guessed a global
flush.

Yeah, would be great to understand how this all works.

As a side question: in regular C spinlocks, can you point me to the
place where the caches get flushed when a lock moves from CPU1 to
CPU2? I spent some time looking at the code, but found nothing myself.
Or this implemented in a different way?

Thanks,
Yury

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 01:34:22PM -0400, Yury Norov wrote:
> On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> > On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > >
> > > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > > identical, and ignoring the former.
> > > > >
> > > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > > 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.
> > > > > >
> > > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > > Rust type system: either callers have shared references &bitmap in
> > > > > > which case the mutations are atomic operations. Or there is a
> > > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > > access.
> > > > >
> > > > > It's not about shared references only. One can take a mutable
> > > > > reference, and still may have a race:
> > > > >
> > > > > CPU1                            CPU2
> > > > >
> > > > > take mut ref
> > > > > bitmap.set() // non-atomic
> > > > > put mut ref
> > > > >                                 take mut ref
> > > > >                                 bitmap.test() // read as 0
> > > > > data propagated to memory
> > > > >                                 bitmap.test() // read as 1
> > > > >
> > > > > To make this scenario impossible, either put or take mut ref
> > > > > should imply global cache flush, because bitmap array is not
> > > > > an internal data for the Bitmap class (only the pointer is).
> > > > >
> > > > > I already asked you to point me to the specification that states that
> > > > > taking mutable reference implies flushing all the caches to the point
> > > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > > it, for the performance considerations.
> > > > 
> > > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > > time you take a mutable reference, but for you to be able to take a
> > > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > > somewhere in between.
> > > > 
> > > 
> > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > > RELEASE-ACQUIRE ordering guarantees that as well.
> > 
> > Not sure what you mean. Atomic set_bit() and clear() bit are often
> > implemented in asm, and there's no acquire-release semantic.
> 
> Sorry, hit 'send' preliminary.
> 
> > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> 
> The problem here is that the object pointed by the 'mut ref' is the
> rust class Bitmap. The class itself allocates an array, which is used
> as an actual storage. The Rust class and C array will likely not share
> cache lines.
> 
> The pointer is returned from a C call bitmap_zalloc(), so I don't
> think it's possible for Rust compiler to realize that the number
> stored in Bitmap is a pointer to data of certain size, and that it
> should be flushed at "mut ref" put... That's why I guessed a global
> flush.
> 

You don't do the flush in the C code either, right? You would rely on
some existing synchronization between threads to make sure CPU2 observes
the memory effect of CPU1 (if that's what you want).

> Yeah, would be great to understand how this all works.
> 
> As a side question: in regular C spinlocks, can you point me to the
> place where the caches get flushed when a lock moves from CPU1 to
> CPU2? I spent some time looking at the code, but found nothing myself.
> Or this implemented in a different way?

Oh I see, the simple answer would be "the fact that cache flushing is
done is implied", now let's take a simple example:

	CPU 1			CPU 2
	=====			=====
	spin_lock();
	x = 1;
	spin_unlock();

				spin_lock();
				r1 = x;		// r1 == 1
				spin_unlock();

that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
1, right? Now let's open the box, with a trivial spinlock implementation:

	CPU 1			CPU 2
	=====			=====
	spin_lock();
	x = 1;
	spin_unlock():
	  smp_store_release(lock, 0);

				spin_lock():
				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
				  
				r1 = x;		// r1 == 1
				spin_unlock();

now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
that means a few things:

1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
	store of CPU1 on the lock.

2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
	on CPU2, it's guaranteed that CPU2 has observed the memory
	effect before the smp_store_release() on CPU1. And this is the
	"implied" part. In the real hardware cache protocal, what the
	smp_store_release() does is basically "flush/invalidate the
	cache and issue the store", therefore since CPU2 observes the
	store part of the smp_store_release(), it's implied that the
	cache flush/invalidate is observed by CPU2 already. Of course
	the actual hardware cache protocal is more complicated, but this
	is the gist of it.

Based on 1 & 2, normally a programer won't need to reason about where
the cache flush is actually issued, but rather the synchronization built
vi the shared variables (in this case, it's the "lock").

Hope this could help.

Regards,
Boqun


> 
> Thanks,
> Yury

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Yury Norov]

On Wed, Apr 23, 2025 at 10:52:19AM -0700, Boqun Feng wrote:
> On Wed, Apr 23, 2025 at 01:34:22PM -0400, Yury Norov wrote:
> > On Wed, Apr 23, 2025 at 01:11:24PM -0400, Yury Norov wrote:
> > > On Wed, Apr 23, 2025 at 09:30:51AM -0700, Boqun Feng wrote:
> > > > On Wed, Apr 23, 2025 at 06:19:18PM +0200, Alice Ryhl wrote:
> > > > > On Wed, Apr 23, 2025 at 5:43 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > >
> > > > > > I received it twice - with timestamps 1:36 and 1:43. Assuming they are
> > > > > > identical, and ignoring the former.
> > > > > >
> > > > > > On Wed, Apr 23, 2025 at 01:43:32PM +0000, Burak Emir wrote:
> > > > > > > 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.
> > > > > > >
> > > > > > > We include set_bit_atomic and clear_bit_atomic operations. One has
> > > > > > > to avoid races with non-atomic operations, which is ensure by the
> > > > > > > Rust type system: either callers have shared references &bitmap in
> > > > > > > which case the mutations are atomic operations. Or there is a
> > > > > > > exclusive reference &mut bitmap, in which case there is no concurrent
> > > > > > > access.
> > > > > >
> > > > > > It's not about shared references only. One can take a mutable
> > > > > > reference, and still may have a race:
> > > > > >
> > > > > > CPU1                            CPU2
> > > > > >
> > > > > > take mut ref
> > > > > > bitmap.set() // non-atomic
> > > > > > put mut ref
> > > > > >                                 take mut ref
> > > > > >                                 bitmap.test() // read as 0
> > > > > > data propagated to memory
> > > > > >                                 bitmap.test() // read as 1
> > > > > >
> > > > > > To make this scenario impossible, either put or take mut ref
> > > > > > should imply global cache flush, because bitmap array is not
> > > > > > an internal data for the Bitmap class (only the pointer is).
> > > > > >
> > > > > > I already asked you to point me to the specification that states that
> > > > > > taking mutable reference implies flushing all the caches to the point
> > > > > > of coherency, but you didn't share it. And I doubt that compiler does
> > > > > > it, for the performance considerations.
> > > > > 
> > > > > The flushing of caches and so on *is* implied. It doesn't happen every
> > > > > time you take a mutable reference, but for you to be able to take a
> > > > > mut ref on CPU2 after releasing it on CPU1, there must be a flush
> > > > > somewhere in between.
> > > > > 
> > > > 
> > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, and if
> > > > CPU1 and CPU2 sync with a store-release+load-acquire, the
> > > > RELEASE-ACQUIRE ordering guarantees that as well.
> > > 
> > > Not sure what you mean. Atomic set_bit() and clear() bit are often
> > > implemented in asm, and there's no acquire-release semantic.
> > 
> > Sorry, hit 'send' preliminary.
> > 
> > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> > 
> > The problem here is that the object pointed by the 'mut ref' is the
> > rust class Bitmap. The class itself allocates an array, which is used
> > as an actual storage. The Rust class and C array will likely not share
> > cache lines.
> > 
> > The pointer is returned from a C call bitmap_zalloc(), so I don't
> > think it's possible for Rust compiler to realize that the number
> > stored in Bitmap is a pointer to data of certain size, and that it
> > should be flushed at "mut ref" put... That's why I guessed a global
> > flush.
> > 
> 
> You don't do the flush in the C code either, right? You would rely on
> some existing synchronization between threads to make sure CPU2 observes
> the memory effect of CPU1 (if that's what you want).
> 
> > Yeah, would be great to understand how this all works.
> > 
> > As a side question: in regular C spinlocks, can you point me to the
> > place where the caches get flushed when a lock moves from CPU1 to
> > CPU2? I spent some time looking at the code, but found nothing myself.
> > Or this implemented in a different way?
> 
> Oh I see, the simple answer would be "the fact that cache flushing is
> done is implied", now let's take a simple example:
> 
> 	CPU 1			CPU 2
> 	=====			=====
> 	spin_lock();
> 	x = 1;
> 	spin_unlock();
> 
> 				spin_lock();
> 				r1 = x;		// r1 == 1
> 				spin_unlock();
> 
> that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
> 1, right? Now let's open the box, with a trivial spinlock implementation:
> 
> 	CPU 1			CPU 2
> 	=====			=====
> 	spin_lock();
> 	x = 1;
> 	spin_unlock():
> 	  smp_store_release(lock, 0);
> 
> 				spin_lock():
> 				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
> 				  
> 				r1 = x;		// r1 == 1
> 				spin_unlock();
> 
> now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
> that means a few things:
> 
> 1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
> 	store of CPU1 on the lock.
> 
> 2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
> 	on CPU2, it's guaranteed that CPU2 has observed the memory
> 	effect before the smp_store_release() on CPU1. And this is the
> 	"implied" part. In the real hardware cache protocal, what the
> 	smp_store_release() does is basically "flush/invalidate the
> 	cache and issue the store", therefore since CPU2 observes the
> 	store part of the smp_store_release(), it's implied that the
> 	cache flush/invalidate is observed by CPU2 already. Of course
> 	the actual hardware cache protocal is more complicated, but this
> 	is the gist of it.
> 
> Based on 1 & 2, normally a programer won't need to reason about where
> the cache flush is actually issued, but rather the synchronization built
> vi the shared variables (in this case, it's the "lock").
> 
> Hope this could help.

Yeah, that helped a lot. Thank you!

So, if this Rust mutable reference is implemented similarly to a
regular spinlock, I've no more questions.

Thanks again for the explanation.

Re: [PATCH v7 0/5] rust: adds Bitmap API, ID pool and bindings

[Boqun Feng]

On Wed, Apr 23, 2025 at 02:00:50PM -0400, Yury Norov wrote:
[...]
> > > > > Yeah, and it's not just "flushing of caches", it's making CPU1's memory
> > > > > operations on the object pointed by "mut ref" observable to CPU2. If
> > > > > CPU1 and CPU2 sync with the a lock, then lock guarantees that, 
> > > 
> > > The problem here is that the object pointed by the 'mut ref' is the
> > > rust class Bitmap. The class itself allocates an array, which is used
> > > as an actual storage. The Rust class and C array will likely not share
> > > cache lines.
> > > 
> > > The pointer is returned from a C call bitmap_zalloc(), so I don't
> > > think it's possible for Rust compiler to realize that the number
> > > stored in Bitmap is a pointer to data of certain size, and that it
> > > should be flushed at "mut ref" put... That's why I guessed a global
> > > flush.
> > > 
> > 
> > You don't do the flush in the C code either, right? You would rely on
> > some existing synchronization between threads to make sure CPU2 observes
> > the memory effect of CPU1 (if that's what you want).
> > 
> > > Yeah, would be great to understand how this all works.
> > > 
> > > As a side question: in regular C spinlocks, can you point me to the
> > > place where the caches get flushed when a lock moves from CPU1 to
> > > CPU2? I spent some time looking at the code, but found nothing myself.
> > > Or this implemented in a different way?
> > 
> > Oh I see, the simple answer would be "the fact that cache flushing is
> > done is implied", now let's take a simple example:
> > 
> > 	CPU 1			CPU 2
> > 	=====			=====
> > 	spin_lock();
> > 	x = 1;
> > 	spin_unlock();
> > 
> > 				spin_lock();
> > 				r1 = x;		// r1 == 1
> > 				spin_unlock();
> > 
> > that is, if CPU 2 gets the lock later than CPU 1, r1 is guaranteed to be
> > 1, right? Now let's open the box, with a trivial spinlock implementation:
> > 
> > 	CPU 1			CPU 2
> > 	=====			=====
> > 	spin_lock();
> > 	x = 1;
> > 	spin_unlock():
> > 	  smp_store_release(lock, 0);
> > 
> > 				spin_lock():
> > 				  while (cmpxchg_acquire(lock, 0, 1) != 0) { }
> > 				  
> > 				r1 = x;		// r1 == 1
> > 				spin_unlock();
> > 
> > now, for CPU2 to acquire the lock, the cmpxchg_acquire() has to succeed,
> > that means a few things:
> > 
> > 1. 	CPU2 observes the lock value to be 0, i.e CPU2 observes the
> > 	store of CPU1 on the lock.
> > 
> > 2.	Since the smp_store_release() on CPU1, and the cmpxchg_acquire()
> > 	on CPU2, it's guaranteed that CPU2 has observed the memory
> > 	effect before the smp_store_release() on CPU1. And this is the
> > 	"implied" part. In the real hardware cache protocal, what the
> > 	smp_store_release() does is basically "flush/invalidate the
> > 	cache and issue the store", therefore since CPU2 observes the
> > 	store part of the smp_store_release(), it's implied that the
> > 	cache flush/invalidate is observed by CPU2 already. Of course
> > 	the actual hardware cache protocal is more complicated, but this
> > 	is the gist of it.
> > 
> > Based on 1 & 2, normally a programer won't need to reason about where
> > the cache flush is actually issued, but rather the synchronization built
> > vi the shared variables (in this case, it's the "lock").
> > 
> > Hope this could help.
> 
> Yeah, that helped a lot. Thank you!
> 
> So, if this Rust mutable reference is implemented similarly to a
> regular spinlock, I've no more questions.
> 

Just to be clear, a mutable reference in Rust is just a pointer (with
special compiler treatment for checking and optimzation), so mutable
reference is not "implemented similarly to a regular spinlock", it's
rather that: if you have a shared data, and you want to get a mutable
reference, you will have to use some synchronization, and maybe 90% case
that's a lock.

So here, what Burak did in Bitmap was defining those non-atomic
functions as requiring mutable references, and if we also get the Sync
and Send part, right. A real user would 90% use a lock to access a
mutable reference to `Bitmap`.

Makes sense?

Regards,
Boqun

> Thanks again for the explanation.

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Alice Ryhl]

On Wed, Apr 23, 2025 at 01:43:36PM +0000, Burak Emir wrote:
> +    loop {
> +        cnt += 1;
> +        if let Some(index) = bitmap.next_bit(i) {

You can use a while let loop here ;)

Alice

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Burak Emir]

On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> So? Can you show your numbers?

For now, I only have numbers that may not be very interesting:

- for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
  22 ns/iteration in C, 32 ns/iteration in Rust.

- for sparse find_next_bit (sparse):
  60 ns/iteration in C, 70 ns/iteration in Rust.

This is a VM running nested in a VM. More importantly: the C helper
method is not inlined.
So we are likely measuring the overhead (plus the extra bounds checking).

I would like to get cross-language inlining to work with thinLTO to
have a more realistic comparison.
However, that is not something that works out of the box.
I am looking at Gary Guo's patch for this:
https://lore.kernel.org/all/20250319205141.3528424-1-gary@garyguo.net/
Currently, I get duplicate symbol errors.

> Can you print the existing C test output back to back with the new one?
> Can you also ask 0-day folks to enable your test in their rust config?

Will look into these. Rong (hi!) is working on LTO for kernel and will
know a lot more than me how Rust will fit in eventually.
IMHO, making cross-language inlining work out of the box will be a
necessary baseline to get Rust performance for hot code.

> > We add a fill_random() method protected by the config in order to
> > maintain the abstraction.
> >
> > Minor fix to the documentation of the corresponding C config
> > FIND_BIT_BENCHMARK, it was mentioning the wrong module name.
>
> Indeed. Can you make it a separate patch, please?

Will do.

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Boqun Feng]

On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > So? Can you show your numbers?
> 
> For now, I only have numbers that may not be very interesting:
> 
> - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
>   22 ns/iteration in C, 32 ns/iteration in Rust.
> 
> - for sparse find_next_bit (sparse):
>   60 ns/iteration in C, 70 ns/iteration in Rust.
> 
> This is a VM running nested in a VM. More importantly: the C helper
> method is not inlined.
> So we are likely measuring the overhead (plus the extra bounds checking).
> 
> I would like to get cross-language inlining to work with thinLTO to
> have a more realistic comparison.
> However, that is not something that works out of the box.
> I am looking at Gary Guo's patch for this:
> https://lore.kernel.org/all/20250319205141.3528424-1-gary@garyguo.net/
> Currently, I get duplicate symbol errors.
> 

You will need to add __rust_helper attribute for the new rust helpers
introduce in your patches. See Gary's patch #2 for example.

Regards,
Boqun

> > Can you print the existing C test output back to back with the new one?
> > Can you also ask 0-day folks to enable your test in their rust config?
> 
> Will look into these. Rong (hi!) is working on LTO for kernel and will
> know a lot more than me how Rust will fit in eventually.
> IMHO, making cross-language inlining work out of the box will be a
> necessary baseline to get Rust performance for hot code.
> 
> > > We add a fill_random() method protected by the config in order to
> > > maintain the abstraction.
> > >
> > > Minor fix to the documentation of the corresponding C config
> > > FIND_BIT_BENCHMARK, it was mentioning the wrong module name.
> >
> > Indeed. Can you make it a separate patch, please?
> 
> Will do.

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Boqun Feng]

On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > So? Can you show your numbers?
> > 
> > For now, I only have numbers that may not be very interesting:
> > 
> > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > 
> > - for sparse find_next_bit (sparse):
> >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > 
> > This is a VM running nested in a VM. More importantly: the C helper
> > method is not inlined.
> > So we are likely measuring the overhead (plus the extra bounds checking).
> > 
> > I would like to get cross-language inlining to work with thinLTO to
> > have a more realistic comparison.
> > However, that is not something that works out of the box.
> > I am looking at Gary Guo's patch for this:
> > https://lore.kernel.org/all/20250319205141.3528424-1-gary@garyguo.net/
> > Currently, I get duplicate symbol errors.
> > 
> 
> You will need to add __rust_helper attribute for the new rust helpers
> introduce in your patches. See Gary's patch #2 for example.
> 

Here you go ;-)

	https://github.com/fbq/linux/tree/rust-inline-bitmap

I rebased on the top of rust-next and applied your patches onto it. The
last one is the necessary bits that enables helper inlining for the new
APIs in your patch. There is also a "TMP" patch in-between, otherwise
INLINE_HELPERS won't work, we need to dig more of it. But anyway, it
works on my machine (TM):

(on x86, in your test function)

000000000028b090 <_RNvNtNtCs3KHxpmQFgFb_6kernel6bitmap5tests40kunit_rust_wrapper_bitmap_set_clear_find>:
  ...
  28b0dd: 48 0f ba 2b 11                btsq    $0x11, (%rbx)

^ this is the "b.set_bit(17);" in bitmap_set_clear_find() test.

Regards,
Boqun
	

> Regards,
> Boqun
> 
> > > Can you print the existing C test output back to back with the new one?
> > > Can you also ask 0-day folks to enable your test in their rust config?
> > 
> > Will look into these. Rong (hi!) is working on LTO for kernel and will
> > know a lot more than me how Rust will fit in eventually.
> > IMHO, making cross-language inlining work out of the box will be a
> > necessary baseline to get Rust performance for hot code.
> > 
> > > > We add a fill_random() method protected by the config in order to
> > > > maintain the abstraction.
> > > >
> > > > Minor fix to the documentation of the corresponding C config
> > > > FIND_BIT_BENCHMARK, it was mentioning the wrong module name.
> > >
> > > Indeed. Can you make it a separate patch, please?
> > 
> > Will do.

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Burak Emir]

On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > So? Can you show your numbers?
> > >
> > > For now, I only have numbers that may not be very interesting:
> > >
> > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > >
> > > - for sparse find_next_bit (sparse):
> > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > >
> > > This is a VM running nested in a VM. More importantly: the C helper
> > > method is not inlined.
> > > So we are likely measuring the overhead (plus the extra bounds checking).
> > >
> > > I would like to get cross-language inlining to work with thinLTO to
> > > have a more realistic comparison.
> > > However, that is not something that works out of the box.
> > > I am looking at Gary Guo's patch for this:
> > > https://lore.kernel.org/all/20250319205141.3528424-1-gary@garyguo.net/
> > > Currently, I get duplicate symbol errors.
> > >
> >
> > You will need to add __rust_helper attribute for the new rust helpers
> > introduce in your patches. See Gary's patch #2 for example.
> >
>
> Here you go ;-)
>
>         https://github.com/fbq/linux/tree/rust-inline-bitmap
>
> I rebased on the top of rust-next and applied your patches onto it. The
> last one is the necessary bits that enables helper inlining for the new
> APIs in your patch. There is also a "TMP" patch in-between, otherwise
> INLINE_HELPERS won't work, we need to dig more of it. But anyway, it
> works on my machine (TM):
>
> (on x86, in your test function)
>
> 000000000028b090 <_RNvNtNtCs3KHxpmQFgFb_6kernel6bitmap5tests40kunit_rust_wrapper_bitmap_set_clear_find>:
>   ...
>   28b0dd: 48 0f ba 2b 11                btsq    $0x11, (%rbx)
>
> ^ this is the "b.set_bit(17);" in bitmap_set_clear_find() test.

Thanks Boqun! I had the same state and got things to build now with
CONFIG_LTO_NONE.
Your work helped me narrow down the possibilities.

Gary's helper-inlining patch in combination of CONFIG_CLANG_LTO_THIN
and CONFIG_FIND_BIT_BENCHMARK_RUST=y gives "duplicate symbol" build
errors.

It does not eve matter here - because  _find_next_bit C functions are
not helpers.

For cross-language inlining, we would need to change the build system
similar to Gary's helper-inlining series, but for *all* object files.
That is what "-flto" does for clang, and "-Clinker-plugin-lto" would
do for rustc.
Instead of the hack of emitting a .bc file, we need all .o files to
contain LLVM bitcode, regardless of whether they come from clang or
rustc.

Thanks,
Burak

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Boqun Feng]

On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > So? Can you show your numbers?
> > > >
> > > > For now, I only have numbers that may not be very interesting:
> > > >
> > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > >
> > > > - for sparse find_next_bit (sparse):
> > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > >
> > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > method is not inlined.
> > > > So we are likely measuring the overhead (plus the extra bounds checking).
> > > >
> > > > I would like to get cross-language inlining to work with thinLTO to
> > > > have a more realistic comparison.
> > > > However, that is not something that works out of the box.
> > > > I am looking at Gary Guo's patch for this:
> > > > https://lore.kernel.org/all/20250319205141.3528424-1-gary@garyguo.net/
> > > > Currently, I get duplicate symbol errors.
> > > >
> > >
> > > You will need to add __rust_helper attribute for the new rust helpers
> > > introduce in your patches. See Gary's patch #2 for example.
> > >
> >
> > Here you go ;-)
> >
> >         https://github.com/fbq/linux/tree/rust-inline-bitmap
> >
> > I rebased on the top of rust-next and applied your patches onto it. The
> > last one is the necessary bits that enables helper inlining for the new
> > APIs in your patch. There is also a "TMP" patch in-between, otherwise
> > INLINE_HELPERS won't work, we need to dig more of it. But anyway, it
> > works on my machine (TM):
> >
> > (on x86, in your test function)
> >
> > 000000000028b090 <_RNvNtNtCs3KHxpmQFgFb_6kernel6bitmap5tests40kunit_rust_wrapper_bitmap_set_clear_find>:
> >   ...
> >   28b0dd: 48 0f ba 2b 11                btsq    $0x11, (%rbx)
> >
> > ^ this is the "b.set_bit(17);" in bitmap_set_clear_find() test.
> 
> Thanks Boqun! I had the same state and got things to build now with
> CONFIG_LTO_NONE.
> Your work helped me narrow down the possibilities.
> 

Great! Is performance number any different?

> Gary's helper-inlining patch in combination of CONFIG_CLANG_LTO_THIN
> and CONFIG_FIND_BIT_BENCHMARK_RUST=y gives "duplicate symbol" build
> errors.
> 
> It does not eve matter here - because  _find_next_bit C functions are
> not helpers.
> 

Yes, I noticed that, but in theory we should have the same performance
as C because C also make the call-jump to _find_next_bit() instead of
inlining it.

> For cross-language inlining, we would need to change the build system
> similar to Gary's helper-inlining series, but for *all* object files.
> That is what "-flto" does for clang, and "-Clinker-plugin-lto" would
> do for rustc.
> Instead of the hack of emitting a .bc file, we need all .o files to
> contain LLVM bitcode, regardless of whether they come from clang or
> rustc.
> 

There are cases where we don't want a full LTO, and so having an option
to get rid of unnecessary calls to the helpers instead of a full LTO is
reasonable IMO. But of course, no reason not to make cross-language
inlining work under LTO.

Regards,
Boqun

> Thanks,
> Burak

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Burak Emir]

On Fri, Apr 25, 2025 at 3:45 PM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> > On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > >
> > > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > > So? Can you show your numbers?
> > > > >
> > > > > For now, I only have numbers that may not be very interesting:
> > > > >
> > > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > > >
> > > > > - for sparse find_next_bit (sparse):
> > > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > > >
> > > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > > method is not inlined.
> > > > > So we are likely measuring the overhead (plus the extra bounds checking).

Alice and I discussed that it may be better to do away with the extra
bounds check.
Micro benchmark, for the upcoming v8 that has the bounds check removed
(and the test changed to >=, as requested):

[] Start testing find_bit() with random-filled bitmap
[] find_next_bit:                 3598165 ns, 164282 iterations
[] find_next_zero_bit:            3626186 ns, 163399 iterations
[] Start testing find_bit() with sparse bitmap
[] find_next_bit:                   40865 ns,    656 iterations
[] find_next_zero_bit:            7100039 ns, 327025 iterations
[] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
random-filled bitmap
[] find_bit_benchmark_rust_module: next_bit:
4572086 ns, 164112 iterations
[] find_bit_benchmark_rust_module: next_zero_bit:
4582930 ns, 163569 iterations
[] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
sparse bitmap
[] find_bit_benchmark_rust_module: next_bit:
42622 ns,    655 iterations
[] find_bit_benchmark_rust_module: next_zero_bit:
8835122 ns, 327026 iterations

cheers,
Burak

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Yury Norov]

On Fri, Apr 25, 2025 at 06:17:59PM +0200, Burak Emir wrote:
> On Fri, Apr 25, 2025 at 3:45 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> > > On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > > > So? Can you show your numbers?
> > > > > >
> > > > > > For now, I only have numbers that may not be very interesting:
> > > > > >
> > > > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > > > >
> > > > > > - for sparse find_next_bit (sparse):
> > > > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > > > >
> > > > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > > > method is not inlined.
> > > > > > So we are likely measuring the overhead (plus the extra bounds checking).
> 
> Alice and I discussed that it may be better to do away with the extra
> bounds check.
> Micro benchmark, for the upcoming v8 that has the bounds check removed
> (and the test changed to >=, as requested):
> 
> [] Start testing find_bit() with random-filled bitmap
> [] find_next_bit:                 3598165 ns, 164282 iterations
> [] find_next_zero_bit:            3626186 ns, 163399 iterations
> [] Start testing find_bit() with sparse bitmap
> [] find_next_bit:                   40865 ns,    656 iterations
> [] find_next_zero_bit:            7100039 ns, 327025 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> random-filled bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 4572086 ns, 164112 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 4582930 ns, 163569 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> sparse bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 42622 ns,    655 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 8835122 ns, 327026 iterations

So I'm lost. You're going to keep those hardenings, but show the
numbers without hardening on VM. Is that right?

Can you please show the numbers on bare-metal with the final
configuration?

Thanks,
Yury

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Burak Emir]

On Sat, Apr 26, 2025 at 3:03 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Fri, Apr 25, 2025 at 06:17:59PM +0200, Burak Emir wrote:
> > On Fri, Apr 25, 2025 at 3:45 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > >
> > > On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> > > > On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > >
> > > > > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > > > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > > > > So? Can you show your numbers?
> > > > > > >
> > > > > > > For now, I only have numbers that may not be very interesting:
> > > > > > >
> > > > > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > > > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > > > > >
> > > > > > > - for sparse find_next_bit (sparse):
> > > > > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > > > > >
> > > > > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > > > > method is not inlined.
> > > > > > > So we are likely measuring the overhead (plus the extra bounds checking).
> >
> > Alice and I discussed that it may be better to do away with the extra
> > bounds check.
> > Micro benchmark, for the upcoming v8 that has the bounds check removed
> > (and the test changed to >=, as requested):
> >
> > [] Start testing find_bit() with random-filled bitmap
> > [] find_next_bit:                 3598165 ns, 164282 iterations
> > [] find_next_zero_bit:            3626186 ns, 163399 iterations
> > [] Start testing find_bit() with sparse bitmap
> > [] find_next_bit:                   40865 ns,    656 iterations
> > [] find_next_zero_bit:            7100039 ns, 327025 iterations
> > [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> > random-filled bitmap
> > [] find_bit_benchmark_rust_module: next_bit:
> > 4572086 ns, 164112 iterations
> > [] find_bit_benchmark_rust_module: next_zero_bit:
> > 4582930 ns, 163569 iterations
> > [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> > sparse bitmap
> > [] find_bit_benchmark_rust_module: next_bit:
> > 42622 ns,    655 iterations
> > [] find_bit_benchmark_rust_module: next_zero_bit:
> > 8835122 ns, 327026 iterations
>
> So I'm lost. You're going to keep those hardenings, but show the
> numbers without hardening on VM. Is that right?

No, I will remove the bounds checks where they are not needed for safety.
Indeed the latest are numbers without hardening in nested VM.

> Can you please show the numbers on bare-metal with the final
> configuration?

Sure, will include in v8 cover letter.

cheers,
Burak

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Alice Ryhl]

On Fri, Apr 25, 2025 at 06:17:59PM +0200, Burak Emir wrote:
> On Fri, Apr 25, 2025 at 3:45 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Fri, Apr 25, 2025 at 02:20:13PM +0200, Burak Emir wrote:
> > > On Fri, Apr 25, 2025 at 12:31 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Thu, Apr 24, 2025 at 09:48:17AM -0700, Boqun Feng wrote:
> > > > > On Thu, Apr 24, 2025 at 06:45:33PM +0200, Burak Emir wrote:
> > > > > > On Wed, Apr 23, 2025 at 6:56 PM Yury Norov <yury.norov@gmail.com> wrote:
> > > > > > > So? Can you show your numbers?
> > > > > >
> > > > > > For now, I only have numbers that may not be very interesting:
> > > > > >
> > > > > > - for find_next_bit,  find_next_zero_bit and find_next_zero_bit (sparse):
> > > > > >   22 ns/iteration in C, 32 ns/iteration in Rust.
> > > > > >
> > > > > > - for sparse find_next_bit (sparse):
> > > > > >   60 ns/iteration in C, 70 ns/iteration in Rust.
> > > > > >
> > > > > > This is a VM running nested in a VM. More importantly: the C helper
> > > > > > method is not inlined.
> > > > > > So we are likely measuring the overhead (plus the extra bounds checking).
> 
> Alice and I discussed that it may be better to do away with the extra
> bounds check.
> Micro benchmark, for the upcoming v8 that has the bounds check removed
> (and the test changed to >=, as requested):
> 
> [] Start testing find_bit() with random-filled bitmap
> [] find_next_bit:                 3598165 ns, 164282 iterations
> [] find_next_zero_bit:            3626186 ns, 163399 iterations
> [] Start testing find_bit() with sparse bitmap
> [] find_next_bit:                   40865 ns,    656 iterations
> [] find_next_zero_bit:            7100039 ns, 327025 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> random-filled bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 4572086 ns, 164112 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 4582930 ns, 163569 iterations
> [] find_bit_benchmark_rust_module: Start testing find_bit() Rust with
> sparse bitmap
> [] find_bit_benchmark_rust_module: next_bit:
> 42622 ns,    655 iterations
> [] find_bit_benchmark_rust_module: next_zero_bit:
> 8835122 ns, 327026 iterations

By the way, if you add assert_eq!(bitmap.len(), BITMAP_LEN) before the
loop you may get the bounds checks optimized out.

Alice

Re: [PATCH v7 3/5] rust: add bitmap API.

[Burak Emir]

On Wed, Apr 23, 2025 at 6:46 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Wed, Apr 23, 2025 at 01:43:35PM +0000, Burak Emir wrote:
> >
> > Provides an abstraction for C bitmap API and bitops operations.
> > We follow the C Bitmap API closely in naming and semantics, with
> > a few differences that take advantage of Rust language facilities
> > and idioms:
> >
> >   * not all operations are exposed yet, to avoid dead code. This commit
> >     includes enough to implement an Android Binder data structure that
> >     was introduced in commit 15d9da3f818c ("binder: use bitmap for
> >     faster descriptor lookup"), namely drivers/android/dbitmap.h. This
> >     is part of upstreaming the Android Binder driver.
> >
> >   * API uses Option types where appropriate
> >
> >   * bound checks are used to treat out-of-bounds access as bug
> >     (hardening). The C operations treat out-of-bounds parameters
> >     as a default case e.g. "not found" which is safe (avoids UB) but
> >     may hide bugs.
>
> Few paragraphs later you say:
>
> > It enables Rust
> > code to be a lot more similar and predictable with respect to C code
>
> If you want to make Rust similar to C (which is good), you need to
> make all that Panic'ing stuff configurable, right?

Yes, I agree with this reasoning in combination with BUG_ON.

> This is what I suggested originally, and this is the right way to go,
> to me.
>
> There was a long discussion few years ago regarding BUG_ON()s in the
> kernel, and the bottomline for it is simple: the kernel has many nice
> isolating and self-debugging features that help to resolve (hopefully)
> non-fatal errors like out-of-bond access, so we should let it try.

In my own words: using BUG_ON to prevent undefined behavior is almost
always going to be more useful than panic.

> Just halting the kernel helps little, particularly it prevents from
> collecting syslogs and other debugging info. You can check git history
> and see how many BUG()s were demoted to WARN()s, or simply dropped.
>
> So, this is again my suggestion: it's OK to have a hardening feature,
> but the panic should be configurable for the reasons:
>  - robustness;
>  - compatibility;
>  - debugability.
>
> To me, this should end up with something like:
>
>   fn bitmap_assert(bool, msg)
>   {
>   #if CONFIG_RUST_HARDENING_PANIC && CONFIG_RUST_BITMAP_HARDENING
>         assert(bool, msg)
>   #elif CONFIG_RUST_BITMAP_HARDENING
>         if (!bool)
>                 pr_err(msg)
>   #else
>         // do nothing; for the best performance.
>   #endif
>   }
>
> This doesn't look difficult anyhow right? But if you find it
> impractical, you can just replace the panic with printing an error.

There are several things at play:
- for the C methods that tolerate out-of-bounds access, the
bounds-check is redundant for safety
- but it is not redundant in terms of API: tolerating out-of-bounds
access is the spec, someone may rely on it
- if we would like a Rust API that is stricter (hardening), it is an
API change (or: a Rust and C API difference).

I will go with your suggestion and do a local (bitmap-specific)
configurable assert (=panic).
This could then later be changed to use a BUG macro.

> After all, this # Panic simply breaks your own coding rules:
>
>   Please note that panicking should be very rare and used only with a good
>   reason. In almost all cases, a fallible approach should be used, typically
>   returning a ``Result``.
>

Bitmap operations are so basic and the API that fallibility does not
make sense to me here.
The Rust API is also constrained by what the C API provides: if C
handles out-of-bounds arguments gracefully, then Rust should, too.
And panicking has the problems you described, so I have come around to
think that Rust needs a BUG_ON macro.

> >   * better naming convention to distinguish non-atomic from atomic
> >     operations: {set,clear}_bit vs {set,clear}_bit_atomic.
> >     The Rust type system ensures that all non-atomic operations
> >     require a &mut reference which amounts to exclusive access.
> >     Using the atomic variants only makes sense when multiple threads
> >     have a shared reference &bitmap which amounts to the interior
> >     mutability pattern.
> >
> >   * optimized to represent the bitmap inline if it would take the space
> >     of a pointer. This saves allocations which is relevant in the
> >     Binder use case.
> >
> > The underlying C bitmap is *not* exposed. This would lose all static
> > guarantees.
> >
> > An alternative route of vendoring an existing Rust bitmap package was
> > considered but suboptimal overall. Reusing the C implementation is
> > preferable for a basic data structure like bitmaps. It enables Rust
> > code to be a lot more similar and predictable with respect to C code
> > that uses the same data structures and enables the use of code that
> > has been tried-and-tested in the kernel.
> >
> > We use the `usize` type for sizes and indices into the bitmap,
> > because Rust generally always uses that type for indices and lengths
> > and it will be more convenient if the API accepts that type. This means
> > that we need to perform some casts to/from u32 and usize, since the C
> > headers use unsigned int instead of size_t/unsigned long for these
> > numbers in some places.
> >
> > Adds new MAINTAINERS section BITMAP API [RUST].
> >
> > Suggested-by: Alice Ryhl <aliceryhl@google.com>
> > Suggested-by: Yury Norov <yury.norov@gmail.com>
> > Signed-off-by: Burak Emir <bqe@google.com>
> > ---
> >  MAINTAINERS           |   7 +
> >  rust/kernel/bitmap.rs | 396 ++++++++++++++++++++++++++++++++++++++++++
> >  rust/kernel/lib.rs    |   1 +
> >  3 files changed, 404 insertions(+)
> >  create mode 100644 rust/kernel/bitmap.rs
> >
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index 1f162f64eded..7d107dc91390 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -4135,6 +4135,13 @@ S:     Maintained
> >  F:   rust/helpers/bitmap.c
> >  F:   rust/helpers/cpumask.c
> >
> > +BITMAP API [RUST]
> > +M:   Alice Ryhl <aliceryhl@google.com>
> > +M:   Burak Emir <bqe@google.com>
> > +R:   Yury Norov <yury.norov@gmail.com>
> > +S:   Maintained
> > +F:   rust/kernel/bitmap.rs
> > +
> >  BITOPS API
> >  M:   Yury Norov <yury.norov@gmail.com>
> >  R:   Rasmus Villemoes <linux@rasmusvillemoes.dk>
> > diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> > new file mode 100644
> > index 000000000000..79ddbef2b028
> > --- /dev/null
> > +++ b/rust/kernel/bitmap.rs
> > @@ -0,0 +1,396 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +// Copyright (C) 2025 Google LLC.
> > +
> > +//! Rust API for bitmap.
> > +//!
> > +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
> > +
> > +use crate::alloc::{AllocError, Flags};
> > +use crate::bindings;
> > +use core::ptr::NonNull;
> > +
> > +/// Holds either a pointer to array of `unsigned long` or a small bitmap.
> > +#[repr(C)]
> > +union BitmapRepr {
> > +    bitmap: usize,
> > +    ptr: NonNull<usize>,
> > +}
> > +
> > +    pub fn last_bit(&self) -> Option<usize> {
>
> [...]
>
> > +        // SAFETY: access is within bounds.
> > +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.nbits) };
> > +        if index == self.nbits {
>
> Here and everywhere, can you please:
>
>         if index >= self.nbits {
>
> I know that bitmap documentation says that index would be exactly
> nbits, but really it was a bad decision. If one day I'll find a safe
> way to relax this to >=, your code will stay untouched.

Done, going to be in v8.

Thanks,
Burak

>
> Thanks,
> Yury

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Yury Norov]

> By the way, if you add assert_eq!(bitmap.len(), BITMAP_LEN) before the
> loop you may get the bounds checks optimized out.

That sounds cheating, isn't?

I think nobody will reject this series because of +15% in performance
test, neither +25%, or whatever reasonable number.

Let's just measure fair numbers and deliver clear maintainable code. 
There's a single user for bitmaps in rust so far, and it's you. So
you're to call if performance is bad for you, not me. I just want
to make sure that your numbers are withing the sane boundaries.

Thanks,
Yury

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[Alice Ryhl]

On Mon, Apr 28, 2025 at 09:21:40AM -0400, Yury Norov wrote:
> > By the way, if you add assert_eq!(bitmap.len(), BITMAP_LEN) before the
> > loop you may get the bounds checks optimized out.
> 
> That sounds cheating, isn't?
> 
> I think nobody will reject this series because of +15% in performance
> test, neither +25%, or whatever reasonable number.
> 
> Let's just measure fair numbers and deliver clear maintainable code. 
> There's a single user for bitmaps in rust so far, and it's you. So
> you're to call if performance is bad for you, not me. I just want
> to make sure that your numbers are withing the sane boundaries.

Right, well, in Binder's case the relevant performance comparison is a
single call to the bitmap's next_zero_bit vs following a sorted linked
list to find the first index that isn't used by an element in the list,
so I'm pretty confident that the bitmap will win no matter what.

Alice

Re: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.

[kernel test robot]

Hi Burak,

kernel test robot noticed the following build errors:

[auto build test ERROR on rust/rust-next]
[also build test ERROR on akpm-mm/mm-nonmm-unstable linus/master v6.15-rc5]
[cannot apply to next-20250507]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Burak-Emir/rust-add-bindings-for-bitmap-h/20250423-214819
base:   https://github.com/Rust-for-Linux/linux rust-next
patch link:    https://lore.kernel.org/r/20250423134344.3888205-6-bqe%40google.com
patch subject: [PATCH v7 4/5] rust: add find_bit_benchmark_rust module.
config: riscv-allyesconfig (https://download.01.org/0day-ci/archive/20250507/202505072334.8gubqjKX-lkp@intel.com/config)
compiler: clang version 16.0.6 (https://github.com/llvm/llvm-project 7cbf1a2591520c2491aa35339f227775f4d3adf6)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250507/202505072334.8gubqjKX-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202505072334.8gubqjKX-lkp@intel.com/

All errors (new ones prefixed by >>):

>> error[E0463]: can't find crate for `core`
   |
   = note: the `riscv64imac-unknown-none-elf` target may not be installed
   = help: consider downloading the target with `rustup target add riscv64imac-unknown-none-elf`
   = help: consider building the standard library from source with `cargo build -Zbuild-std`

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki