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

[PATCH v8 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.

A benchmark using a production configuration shows performance on par
with C:

```
              Start testing find_bit() with random-filled bitmap
[    6.974435] find_next_bit:                  944136 ns, 163996 iterations
[    6.982039] find_next_zero_bit:             981618 ns, 163685 iterations
[    6.989460] find_last_bit:                  800630 ns, 163996 iterations
[    7.004710] find_nth_bit:                  8627435 ns,  16281 iterations
[    7.013791] find_first_bit:                2459789 ns,  16282 iterations
[    7.054645] find_first_and_bit:           34227540 ns,  32733 iterations
[    7.061743] find_next_and_bit:              474530 ns,  73676 iterations
[    7.068365] 
               Start testing find_bit() with sparse bitmap
[    7.075035] find_next_bit:                   11394 ns,    656 iterations
[    7.083579] find_next_zero_bit:            1920337 ns, 327025 iterations
[    7.090213] find_last_bit:                   12061 ns,    656 iterations
[    7.100121] find_nth_bit:                  3279811 ns,    655 iterations
[    7.107930] find_first_bit:                1188115 ns,    656 iterations
[    7.114558] find_first_and_bit:               3730 ns,      1 iterations
[    7.121184] find_next_and_bit:                4679 ns,      1 iterations
[    7.127805] find_bit_benchmark_rust_module: Start testing find_bit() Rust with random-filled bitmap
[    7.138550] find_bit_benchmark_rust_module: next_bit:                       999542 ns, 163592 iterations
[    7.148974] find_bit_benchmark_rust_module: next_zero_bit:                 1053432 ns, 164088 iterations
[    7.158342] find_bit_benchmark_rust_module: Start testing find_bit() Rust with sparse bitmap
[    7.166718] find_bit_benchmark_rust_module: next_bit:                        11474 ns,    655 iterations
[    7.178143] find_bit_benchmark_rust_module: next_zero_bit:                 2056913 ns, 327025 iterations
```

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 v8 of a patch introducing Rust bitmap API [v7]. Thanks
for all the helpful comments, this series has improved significantly
as a result of your work.

Changes v7 --> v8:
- added Acked-by for bindings patches
- add RUST_BITMAP_HARDENED config, making the extra bound-checks configurable.
  This is added to security/Kconfig.hardening 
- changed checks of `index` return value to >=
- removed change to FIND_BIT_BENCHMARK

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 [v7] https://lore.kernel.org/rust-for-linux/20250423134344.3888205-2-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               |  13 +
 lib/Makefile                    |   1 +
 lib/find_bit_benchmark_rust.rs  |  94 +++++++
 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           | 429 ++++++++++++++++++++++++++++++++
 rust/kernel/id_pool.rs          | 201 +++++++++++++++
 rust/kernel/lib.rs              |   2 +
 security/Kconfig.hardening      |   9 +
 12 files changed, 800 insertions(+)
 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.1101.gccaa498523-goog

[PATCH v8 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>
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 d48dd6726fe6..86cae0ca5287 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4124,6 +4124,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 1e7c84df7252..92721d165e35 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.1101.gccaa498523-goog

[PATCH v8 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>
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 86cae0ca5287..04d6727e944c 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4141,6 +4141,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 92721d165e35..4de8ac390241 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.1101.gccaa498523-goog

[PATCH v8 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:

  * We leverage Rust type system guarantees as follows:

    * Ownership transfer of a Bitmap is restricted so that it cannot
    be passed between threads (does not implement `Send`).

    * all (non-atomic) mutating operations require a &mut reference which
    amounts to exclusive access.

    * It is permissible to pass shared references &Bitmap between
    threads, and we expose atomic operations through interior mutability.
    Since these atomic operations do not provide any ordering guarantees,
    we mark these as `unsafe`. Anyone who calls the atomic methods needs
    to document that the lack of ordering is safe.

  * The Rust API offers `{set,clear}_bit` vs `{set,clear}_bit_atomic`,
    which is different from the C naming convention (set_bit vs __set_bit).

  * we include enough operations for the API to be useful, but not all
    operations are exposed yet in order to avoid dead code. This commit
    includes enough to enable a Rust implementation of an Android Binder
    data structure that was introduced in commit 15d9da3f818c ("binder:
    use bitmap for faster descriptor lookup"), which can be found in
    drivers/android/dbitmap.h. We need this in order to upstream the Rust
    port of Android Binder driver.

  * We follow the C API closely and fine-grained approach to safety:

    * Low-level bit-ops methods get a safe API with bounds checks.

    * methods correspond to find_* C methods tolerate out-of-bounds
    arguments. Since these are already safe we the same behavior, and
    return results using `Option` types to represent "not found".

  * the Rust API is 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.

  * Bounds checks where out-of-bounds values would not result in
    immediate access faults are configured via a RUST_BITMAP_HARDENED
    config.

The underlying C bitmap is *not* exposed, and must never be exposed
(except in tests). Exposing the representation would lose all static
guarantees, and moreover would prevent the optimized representation of
short bitmaps.

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, with the same performance
characteristics whenever possible.

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      | 415 +++++++++++++++++++++++++++++++++++++
 rust/kernel/lib.rs         |   1 +
 security/Kconfig.hardening |   9 +
 4 files changed, 432 insertions(+)
 create mode 100644 rust/kernel/bitmap.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index 04d6727e944c..565eaa015d9e 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4127,6 +4127,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..943dbef7948b
--- /dev/null
+++ b/rust/kernel/bitmap.rs
@@ -0,0 +1,415 @@
+// 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>,
+}
+
+macro_rules! bitmap_hardening_assert {
+    ($cond:expr, $($arg:tt)+) => {
+        #[cfg(RUST_BITMAP_HARDENED)]
+        assert!($e, $($arg)*);
+    }
+}
+
+/// 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,
+}
+
+/// Enable unsynchronized concurrent access to [`Bitmap`] through shared references.
+///
+/// # Safety
+///
+/// * When no thread performs any mutations, concurrent access is safe.
+/// * Mutations are permitted through atomic operations and interior mutability.
+///   All such methods are marked unsafe, to account for the lack of ordering
+///   guarantees. Callers must acknowledge that updates may be observed in any
+///   order.
+unsafe impl Sync for Bitmap {}
+
+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.
+    ///
+    /// ATTENTION: The naming convention differs from C, where the corresponding
+    /// function is called `set_bit`.
+    ///
+    /// # Safety
+    ///
+    /// This is a relaxed atomic operation (no implied memory barriers, no
+    /// ordering guarantees). The caller must ensure that this is safe, as
+    /// the compiler cannot prevent code with an exclusive reference from
+    /// calling atomic operations.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub unsafe 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 the caller has ensured that
+        // there is no mix of non-atomic and atomic operations.
+        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.
+    ///
+    /// ATTENTION: The naming convention differs from C, where the corresponding
+    /// function is called `clear_bit`.
+    ///
+    /// # Safety
+    ///
+    /// This is a relaxed atomic operation (no implied memory barriers, no
+    /// ordering guarantees). The caller must ensure that this is safe, as
+    /// the compiler cannot prevent code with an exclusive reference from
+    /// calling atomic operations.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `index` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub unsafe 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 the caller has ensured that
+        // there is no mix of non-atomic and atomic operations.
+        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: `_find_next_bit` access is within bounds due to invariant.
+        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`.
+    /// Returns `None` if `start` is greater of equal than `self.nbits`.
+    #[inline]
+    pub fn next_bit(&self, start: usize) -> Option<usize> {
+        bitmap_hardening_assert!(start < self.nbits, "`start` must be < {} was {}", self.nbits, start);
+        // SAFETY: `_find_next_bit` tolerates out-of-bounds arguments and returns a
+        // value larger than or equal to `self.nbits` in that case.
+        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`.
+    /// Returns `None` if `start` is greater than or equal to `self.nbits`.
+    #[inline]
+    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
+        bitmap_hardening_assert!(start < self.nbits, "`start` must be < {} was {}", self.nbits, start);
+        // SAFETY: `_find_next_zero_bit` tolerates out-of-bounds arguments and returns a
+        // value larger than or equal to `self.nbits` in that case.
+        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_out_of_bounds() {
+        let mut b = Bitmap::new(128, GFP_KERNEL).unwrap();
+
+        assert_eq!(None, b.next_bit(2048));
+        assert_eq!(None, b.next_zero_bit(2048));
+        assert_eq!(None, b.last_bit(2048));
+    }
+
+    #[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 de07aadd1ff5..8c4161cd82ac 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)]
diff --git a/security/Kconfig.hardening b/security/Kconfig.hardening
index 3fe9d7b945c4..926665bbc8f2 100644
--- a/security/Kconfig.hardening
+++ b/security/Kconfig.hardening
@@ -324,6 +324,15 @@ config LIST_HARDENED
 
 	  If unsure, say N.
 
+config RUST_BITMAP_HARDENED
+	bool "Check integrity of linked list manipulation"
+	help
+	  Enables additional assertions in the Rust Bitmap API to catch
+	  arguments that are not guaranteed to result in an immediate access
+	  fault.
+
+	  If unsure, say N.
+
 config BUG_ON_DATA_CORRUPTION
 	bool "Trigger a BUG when data corruption is detected"
 	select LIST_HARDENED
-- 
2.49.0.1101.gccaa498523-goog

[PATCH v8 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.

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               | 13 +++++
 lib/Makefile                    |  1 +
 lib/find_bit_benchmark_rust.rs  | 94 +++++++++++++++++++++++++++++++++
 rust/bindings/bindings_helper.h |  1 +
 rust/kernel/bitmap.rs           | 14 +++++
 6 files changed, 124 insertions(+)
 create mode 100644 lib/find_bit_benchmark_rust.rs

diff --git a/MAINTAINERS b/MAINTAINERS
index 565eaa015d9e..943d85ed1876 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4132,6 +4132,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..37a07559243e 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -2605,6 +2605,19 @@ config FIND_BIT_BENCHMARK
 
 	  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..13830477a8d2
--- /dev/null
+++ b/lib/find_bit_benchmark_rust.rs
@@ -0,0 +1,94 @@
+// 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_next_bit(bitmap: &Bitmap) {
+    let mut time = Ktime::ktime_get();
+    let mut cnt = 0;
+    let mut i = 0;
+
+    while let Some(index) = bitmap.next_bit(i) {
+        cnt += 1;
+        i = index + 1;
+    }
+
+    time = Ktime::ktime_get() - time;
+    pr_err!(
+        "next_bit:           {:18} ns, {:6} iterations\n",
+        time.to_ns(),
+        cnt
+    );
+}
+
+fn test_next_zero_bit(bitmap: &Bitmap) {
+    let mut time = Ktime::ktime_get();
+    let mut cnt = 0;
+    let mut i = 0;
+
+    while let Some(index) = bitmap.next_zero_bit(i) {
+        cnt += 1;
+        i = index + 1;
+    }
+
+    time = Ktime::ktime_get() - time;
+    pr_err!(
+        "next_zero_bit:      {:18} ns, {:6} 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_next_bit(&bitmap);
+    test_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_next_bit(&bitmap);
+    test_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 943dbef7948b..fb0c687420cd 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -124,6 +124,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.1101.gccaa498523-goog

[PATCH v8 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 943d85ed1876..bc95d98f266b 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4134,6 +4134,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 8c4161cd82ac..d7def807900a 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.1101.gccaa498523-goog

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

[Yury Norov]

On Mon, May 19, 2025 at 04:17:04PM +0000, Burak Emir wrote:
> Microbenchmark protected by a config FIND_BIT_BENCHMARK_RUST,
> following `find_bit_benchmark.c` but testing the Rust Bitmap API.

I already asked this: please print the output of this test together
wit C version, and please make sure it's collected on bare metal
machine.
 
> We add a fill_random() method protected by the config in order to
> maintain the abstraction.
> 
> 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               | 13 +++++
>  lib/Makefile                    |  1 +
>  lib/find_bit_benchmark_rust.rs  | 94 +++++++++++++++++++++++++++++++++
>  rust/bindings/bindings_helper.h |  1 +
>  rust/kernel/bitmap.rs           | 14 +++++
>  6 files changed, 124 insertions(+)
>  create mode 100644 lib/find_bit_benchmark_rust.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 565eaa015d9e..943d85ed1876 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4132,6 +4132,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..37a07559243e 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -2605,6 +2605,19 @@ config FIND_BIT_BENCHMARK
>  
>  	  If unsure, say N.
>  
> +config FIND_BIT_BENCHMARK_RUST

Shouldn't this depend on config RUST, and maybe something else?

> +	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..13830477a8d2
> --- /dev/null
> +++ b/lib/find_bit_benchmark_rust.rs
> @@ -0,0 +1,94 @@
> +// 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_next_bit(bitmap: &Bitmap) {
> +    let mut time = Ktime::ktime_get();
> +    let mut cnt = 0;
> +    let mut i = 0;
> +
> +    while let Some(index) = bitmap.next_bit(i) {
> +        cnt += 1;
> +        i = index + 1;
> +    }
> +
> +    time = Ktime::ktime_get() - time;
> +    pr_err!(
> +        "next_bit:           {:18} ns, {:6} iterations\n",
> +        time.to_ns(),
> +        cnt
> +    );
> +}
> +
> +fn test_next_zero_bit(bitmap: &Bitmap) {
> +    let mut time = Ktime::ktime_get();
> +    let mut cnt = 0;
> +    let mut i = 0;
> +
> +    while let Some(index) = bitmap.next_zero_bit(i) {
> +        cnt += 1;
> +        i = index + 1;
> +    }
> +
> +    time = Ktime::ktime_get() - time;
> +    pr_err!(
> +        "next_zero_bit:      {:18} ns, {:6} 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_next_bit(&bitmap);
> +    test_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_next_bit(&bitmap);
> +    test_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,

Can you explain the meaning of 'type' section? To me your type is too
unique. This way, we'll end up having the number of types equal to
the number of modules.

Maybe just 'Benchmark'?

> +    name: "find_bit_benchmark_rust_module",
> +    authors: ["Rust for Linux Contributors"],

To me it's pretty useless. I think this 'authors' section exists to
help those having troubles with the module to reach the right people.
Can you please add your name and email here?

> +    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 943dbef7948b..fb0c687420cd 100644
> --- a/rust/kernel/bitmap.rs
> +++ b/rust/kernel/bitmap.rs
> @@ -124,6 +124,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.1101.gccaa498523-goog

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

[Miguel Ojeda]

On Mon, May 19, 2025 at 7:39 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> To me it's pretty useless. I think this 'authors' section exists to
> help those having troubles with the module to reach the right people.
> Can you please add your name and email here?

Yeah, we used that back in the initial merge since there were a bunch
of contributors and because the samples were fairly "core".

Nowadays, and especially for concrete things that are not "used by
everybody", indeed it is best to use concrete names.

Thanks!

Cheers,
Miguel

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

[Yury Norov]

On Mon, May 19, 2025 at 04:17:03PM +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:
> 
>   * We leverage Rust type system guarantees as follows:
> 
>     * Ownership transfer of a Bitmap is restricted so that it cannot
>     be passed between threads (does not implement `Send`).

Can you explain why you decided to not implement it? You can 'share' a
reference, but prohibit 'sending' it...

>     * all (non-atomic) mutating operations require a &mut reference which
>     amounts to exclusive access.
> 
>     * It is permissible to pass shared references &Bitmap between
>     threads, and we expose atomic operations through interior mutability.
>     Since these atomic operations do not provide any ordering guarantees,
>     we mark these as `unsafe`. Anyone who calls the atomic methods needs
>     to document that the lack of ordering is safe.
> 
>   * The Rust API offers `{set,clear}_bit` vs `{set,clear}_bit_atomic`,
>     which is different from the C naming convention (set_bit vs __set_bit).
> 
>   * we include enough operations for the API to be useful, but not all
>     operations are exposed yet in order to avoid dead code. This commit

This sentence and the following one say the same thing. Can you please
rephrase?

>     includes enough to enable a Rust implementation of an Android Binder
>     data structure that was introduced in commit 15d9da3f818c ("binder:
>     use bitmap for faster descriptor lookup"), which can be found in
>     drivers/android/dbitmap.h. We need this in order to upstream the Rust
>     port of Android Binder driver.
> 
>   * We follow the C API closely and fine-grained approach to safety:
> 
>     * Low-level bit-ops methods get a safe API with bounds checks.
> 
>     * methods correspond to find_* C methods tolerate out-of-bounds
>     arguments. Since these are already safe we the same behavior, and
>     return results using `Option` types to represent "not found".

Nit: the above 2 lines look misaligned. Everywhere else you align
items such that new lines under asterisk align with the first
character, not the asterisk itself.

> 
>   * the Rust API is optimized to represent the bitmap inline if it would
>     take the space of a pointer. This saves allocations which is

s/take the space of/fits into/

>     relevant in the Binder use case.
> 
>   * Bounds checks where out-of-bounds values would not result in
>     immediate access faults are configured via a RUST_BITMAP_HARDENED
>     config.
> 
> The underlying C bitmap is *not* exposed, and must never be exposed
> (except in tests). Exposing the representation would lose all static
> guarantees, and moreover would prevent the optimized representation of
> short bitmaps.

Does it mean that all existing kernel bitmaps declared in C are not
accessible in Rust as well?

> 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, with the same performance
> characteristics whenever possible.

This should go in cover letter as well. Did you run any performance
tests against the native bitmaps?
 
> 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      | 415 +++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs         |   1 +
>  security/Kconfig.hardening |   9 +
>  4 files changed, 432 insertions(+)
>  create mode 100644 rust/kernel/bitmap.rs
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 04d6727e944c..565eaa015d9e 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4127,6 +4127,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..943dbef7948b
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,415 @@
> +// 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>,
> +}
> +
> +macro_rules! bitmap_hardening_assert {
> +    ($cond:expr, $($arg:tt)+) => {
> +        #[cfg(RUST_BITMAP_HARDENED)]
> +        assert!($e, $($arg)*);
> +    }
> +}
> +
> +/// 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,
> +}
> +
> +/// Enable unsynchronized concurrent access to [`Bitmap`] through shared references.
> +///
> +/// # Safety
> +///
> +/// * When no thread performs any mutations, concurrent access is safe.
> +/// * Mutations are permitted through atomic operations and interior mutability.
> +///   All such methods are marked unsafe, to account for the lack of ordering
> +///   guarantees. Callers must acknowledge that updates may be observed in any
> +///   order.
> +unsafe impl Sync for Bitmap {}
> +
> +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
> +        );

Shouldn't this assertion be protected with hardening too? I already
said that: panicking on  out-of-boundary access with hardening
disabled is a wrong way to go.

Can you turn your bitmap_hardening_assert() to just bitmap_assert(),
which panics only if hardening is enabled, and otherwise just prints
error with pr_err()?

Did you measure performance impact of hardening? Are those numbers in
cover letter collected with hardening enabled or disabled? If
performance impact is measurable, it should be mentioned in config
description.

> +        // SAFETY: Bit `index` is within bounds.
> +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
> +    /// Set bit with index `index`, atomically.
> +    ///
> +    /// ATTENTION: The naming convention differs from C, where the corresponding
> +    /// function is called `set_bit`.
> +    ///
> +    /// # Safety
> +    ///
> +    /// This is a relaxed atomic operation (no implied memory barriers, no
> +    /// ordering guarantees). The caller must ensure that this is safe, as
> +    /// the compiler cannot prevent code with an exclusive reference from
> +    /// calling atomic operations.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub unsafe 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 the caller has ensured that
> +        // there is no mix of non-atomic and atomic operations.
> +        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.
> +    ///
> +    /// ATTENTION: The naming convention differs from C, where the corresponding
> +    /// function is called `clear_bit`.
> +    ///
> +    /// # Safety
> +    ///
> +    /// This is a relaxed atomic operation (no implied memory barriers, no
> +    /// ordering guarantees). The caller must ensure that this is safe, as

Memory barriers is an implementation of 'ordering guarantees', so all
this sounds tautology.

> +    /// the compiler cannot prevent code with an exclusive reference from
> +    /// calling atomic operations.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub unsafe 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 the caller has ensured that
> +        // there is no mix of non-atomic and atomic operations.
> +        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: `_find_next_bit` access is within bounds due to invariant.
> +        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`.
> +    /// Returns `None` if `start` is greater of equal than `self.nbits`.
> +    #[inline]
> +    pub fn next_bit(&self, start: usize) -> Option<usize> {
> +        bitmap_hardening_assert!(start < self.nbits, "`start` must be < {} was {}", self.nbits, start);
> +        // SAFETY: `_find_next_bit` tolerates out-of-bounds arguments and returns a
> +        // value larger than or equal to `self.nbits` in that case.
> +        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`.
> +    /// Returns `None` if `start` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub fn next_zero_bit(&self, start: usize) -> Option<usize> {
> +        bitmap_hardening_assert!(start < self.nbits, "`start` must be < {} was {}", self.nbits, start);
> +        // SAFETY: `_find_next_zero_bit` tolerates out-of-bounds arguments and returns a
> +        // value larger than or equal to `self.nbits` in that case.
> +        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_out_of_bounds() {
> +        let mut b = Bitmap::new(128, GFP_KERNEL).unwrap();
> +
> +        assert_eq!(None, b.next_bit(2048));
> +        assert_eq!(None, b.next_zero_bit(2048));
> +        assert_eq!(None, b.last_bit(2048));
> +    }
> +
> +    #[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 de07aadd1ff5..8c4161cd82ac 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)]
> diff --git a/security/Kconfig.hardening b/security/Kconfig.hardening
> index 3fe9d7b945c4..926665bbc8f2 100644
> --- a/security/Kconfig.hardening
> +++ b/security/Kconfig.hardening
> @@ -324,6 +324,15 @@ config LIST_HARDENED
>  
>  	  If unsure, say N.
>  
> +config RUST_BITMAP_HARDENED
> +	bool "Check integrity of linked list manipulation"

Wah?

> +	help
> +	  Enables additional assertions in the Rust Bitmap API to catch
> +	  arguments that are not guaranteed to result in an immediate access
> +	  fault.
> +
> +	  If unsure, say N.
> +
>  config BUG_ON_DATA_CORRUPTION
>  	bool "Trigger a BUG when data corruption is detected"
>  	select LIST_HARDENED
> -- 
> 2.49.0.1101.gccaa498523-goog

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

[Yury Norov]

On Mon, May 19, 2025 at 04:17:00PM +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.
> 
> This version includes an optimization to represent the bitmap inline,
> as suggested by Yury.
> 
> A benchmark using a production configuration shows performance on par
> with C:

This should also go in corresponding patch. 'On par' is not a number.
Can you calculate percents? It looks like +7% for next_zero_bit. For
some application this may be a significant number.

Did you enable hardening? Did you estimate confidential interval?
Maybe it's just a noise...

> 
> ```
>               Start testing find_bit() with random-filled bitmap
> [    6.974435] find_next_bit:                  944136 ns, 163996 iterations
> [    6.982039] find_next_zero_bit:             981618 ns, 163685 iterations
> [    6.989460] find_last_bit:                  800630 ns, 163996 iterations
> [    7.004710] find_nth_bit:                  8627435 ns,  16281 iterations
> [    7.013791] find_first_bit:                2459789 ns,  16282 iterations
> [    7.054645] find_first_and_bit:           34227540 ns,  32733 iterations
> [    7.061743] find_next_and_bit:              474530 ns,  73676 iterations
> [    7.068365] 
>                Start testing find_bit() with sparse bitmap
> [    7.075035] find_next_bit:                   11394 ns,    656 iterations
> [    7.083579] find_next_zero_bit:            1920337 ns, 327025 iterations
> [    7.090213] find_last_bit:                   12061 ns,    656 iterations
> [    7.100121] find_nth_bit:                  3279811 ns,    655 iterations
> [    7.107930] find_first_bit:                1188115 ns,    656 iterations
> [    7.114558] find_first_and_bit:               3730 ns,      1 iterations
> [    7.121184] find_next_and_bit:                4679 ns,      1 iterations
> [    7.127805] find_bit_benchmark_rust_module: Start testing find_bit() Rust with random-filled bitmap
> [    7.138550] find_bit_benchmark_rust_module: next_bit:                       999542 ns, 163592 iterations
> [    7.148974] find_bit_benchmark_rust_module: next_zero_bit:                 1053432 ns, 164088 iterations
> [    7.158342] find_bit_benchmark_rust_module: Start testing find_bit() Rust with sparse bitmap
> [    7.166718] find_bit_benchmark_rust_module: next_bit:                        11474 ns,    655 iterations
> [    7.178143] find_bit_benchmark_rust_module: next_zero_bit:                 2056913 ns, 327025 iterations
> ```

So, your output exceeds 80- and even 100-chars limit. Can you drop
that useless "find_bit_benchmark_rust_module:" part?

Thanks,
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 v8 of a patch introducing Rust bitmap API [v7]. Thanks
> for all the helpful comments, this series has improved significantly
> as a result of your work.
> 
> Changes v7 --> v8:
> - added Acked-by for bindings patches
> - add RUST_BITMAP_HARDENED config, making the extra bound-checks configurable.
>   This is added to security/Kconfig.hardening 
> - changed checks of `index` return value to >=
> - removed change to FIND_BIT_BENCHMARK
> 
> 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 [v7] https://lore.kernel.org/rust-for-linux/20250423134344.3888205-2-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               |  13 +
>  lib/Makefile                    |   1 +
>  lib/find_bit_benchmark_rust.rs  |  94 +++++++
>  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           | 429 ++++++++++++++++++++++++++++++++
>  rust/kernel/id_pool.rs          | 201 +++++++++++++++
>  rust/kernel/lib.rs              |   2 +
>  security/Kconfig.hardening      |   9 +
>  12 files changed, 800 insertions(+)
>  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.1101.gccaa498523-goog

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

[Jann Horn]

On Mon, May 19, 2025 at 6:24 PM Burak Emir <bqe@google.com> wrote:
> +    /// Set bit with index `index`, atomically.
> +    ///
> +    /// ATTENTION: The naming convention differs from C, where the corresponding
> +    /// function is called `set_bit`.
> +    ///
> +    /// # Safety
> +    ///
> +    /// This is a relaxed atomic operation (no implied memory barriers, no
> +    /// ordering guarantees). The caller must ensure that this is safe, as
> +    /// the compiler cannot prevent code with an exclusive reference from
> +    /// calling atomic operations.

How can atomic operations through an exclusive reference be unsafe?
You can't have a data race between two atomic operations, and an
exclusive reference should anyway prevent any concurrency, right?

> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if `index` is greater than or equal to `self.nbits`.
> +    #[inline]
> +    pub unsafe 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 the caller has ensured that
> +        // there is no mix of non-atomic and atomic operations.

Aren't non-atomic operations only possible through a mutable
reference? And doesn't the rust compiler enforce that, if someone
holds a mutable reference, nobody else can hold any reference at all?

You wrote yourself above: "all (non-atomic) mutating operations
require a &mut reference which amounts to exclusive access."

I don't understand what's going on here, unless you're saying that
Rust does not enforce that an object ownership transfer between
threads has proper RELEASE/ACQUIRE (or RELEASE/CONSUME) memory
ordering or something like that?

> +        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
> +    }

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

[Yury Norov]

On Mon, May 19, 2025 at 04:17:05PM +0000, Burak Emir wrote:
> 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 943d85ed1876..bc95d98f266b 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4134,6 +4134,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.

Maybe 'unset' or 'free' instead of 'zero'?

> +///
> +/// The ID pool can grow or shrink as needed. It has been designed

s/can/may/. You don't implement automatic adjustment of a pool
capacity, but from this comment one may conclude that the pool  
may grow or shrink by itself. Can you instead say: the Capacity
of IDs may be adjusted by user as needed. Or something like that.

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

Those 'bits' are 'IDs' now. I think the 1st parameter name should
reflect that: num_ids, or something.

> +        let map = Bitmap::new(nbits, flags)?;
> +        Ok(Self { map })
> +    }

What for do you split new() and alloc()? When I call 'new()' method, I
expect it will initialize all the fields.

Or I misunderstand something?

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


So, I don't understand what for do you have this 'pool.shrink_alloc()'
line after the 'new()' call. Thinking object-oriented, when I create
a new object, and receive OK, I can use it immediately. IIUC, I can't
request an ID immediately after creating an IdPool.

> +    /// ```
> +    #[inline]
> +    pub fn shrink_alloc(&self) -> Option<AllocRequest> {
> +        let len = self.map.len();
> +        if len <= bindings::BITS_PER_LONG as usize {
> +            return None;
> +        }

How that? If I want to shrink from 60 to say 30 IDs, I expect that
you will not allow me to allocate 31st ID. But the above code makes
the whole function a no-op...

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

Can you use the 'a/2' style instead of this shifts?

> +                } else {
> +                    None
> +                }
> +            }
> +            None => Some(AllocRequest {
> +                nbits: bindings::BITS_PER_LONG as usize,
> +            }),

Can you reorder the logic such that non-error path will have no extra
indentations?

> +        }
> +    }
> +
> +    /// Shrinks pool by using a new `Bitmap`, if still possible.
> +    #[inline]

I don't understand it. You have shrink_alloc(), which indeed allocates
something, and you have just 'shrink(). And it also allocates before
using the copy_and_extend().

Can you elaborate what for do you need 2 versions of 'shrink'?

> +    pub fn shrink(&mut self, mut resizer: PoolResizer) {

I believe your users will be more thankful if you just allow them to
shrink their ID pools without all that intermediate objects, like:
        my_pool.shrink(100);

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

Again, can you please have non-error path as non-indented as possible?

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

What if I release an empty ID? Maybe emit a warning?

> +    }
> +}

I think I totally miss the idea of PoolResizers here. The standard
dynamic array API looks like this:

        new(capacity)     -> IdPool
        drop(IdPool)      -> void
        acquire()         -> int
        release(id)       -> bool       // True if had been allocated
        acquire_next(id)* -> int        
        get_capacity()    -> int
        set_capacity(cap) -> bool
        num_ids()         -> int

 * This one is pretty rare.  Are you sure you need it?

Your API looks weird with those AllocRequests and PoolResizers,
and TBH I don't understand how that would help your users.

Can you please consider a more standard API?

Thanks,
Yury

> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index 8c4161cd82ac..d7def807900a 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.1101.gccaa498523-goog

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

[Burak Emir]

On Mon, May 19, 2025 at 9:01 PM Jann Horn <jannh@google.com> wrote:
>
> On Mon, May 19, 2025 at 6:24 PM Burak Emir <bqe@google.com> wrote:
> > +    /// Set bit with index `index`, atomically.
> > +    ///
> > +    /// ATTENTION: The naming convention differs from C, where the corresponding
> > +    /// function is called `set_bit`.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// This is a relaxed atomic operation (no implied memory barriers, no
> > +    /// ordering guarantees). The caller must ensure that this is safe, as
> > +    /// the compiler cannot prevent code with an exclusive reference from
> > +    /// calling atomic operations.
>
> How can atomic operations through an exclusive reference be unsafe?
> You can't have a data race between two atomic operations, and an
> exclusive reference should anyway prevent any concurrency, right?

The atomic operations take a &self (shared reference).

The patch is missing the implementation of Sync for now. With that,
one would get concurrent write access through shared references.

The "unsafe" here should serve as reminder to argue why it is ok to
not have any ordering guarantees.

The last sentence is supposed to say: when you have a &mut bitmap, you
can reborrow it as &bitmap, and then happily call this atomic op.
Even though it is unnecessary.

It is unsafe because if one has shared refs on multiple threads, one
needs to be ready to observe updates in any order.

Does it make more sense now? I am open to ideas how to describe this better.


> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub unsafe 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 the caller has ensured that
> > +        // there is no mix of non-atomic and atomic operations.
>
> Aren't non-atomic operations only possible through a mutable
> reference? And doesn't the rust compiler enforce that, if someone
> holds a mutable reference, nobody else can hold any reference at all?
>
> You wrote yourself above: "all (non-atomic) mutating operations
> require a &mut reference which amounts to exclusive access."

As noted above, an exclusive ref can always be reborrowed as a shared ref.

> I don't understand what's going on here, unless you're saying that
> Rust does not enforce that an object ownership transfer between
> threads has proper RELEASE/ACQUIRE (or RELEASE/CONSUME) memory
> ordering or something like that?

Indeed without the Sync implementation, it does not make sense to have
atomic ops that take &self.
Sorry for the confusion, I should have added the Sync implementation.

The normal scenario is that concurrent access would be accompanied by
synchronization through a lock.
For things where the order does not matter, something like counters,
using the atomic ops would be ok.

Ownership transfer between threads (sending) is not possible right
now, unless we implement also `Send`.

> > +        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };
> > +    }

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

[Burak Emir]

On Mon, May 19, 2025 at 10:07 PM Burak Emir <bqe@google.com> wrote:
>
> On Mon, May 19, 2025 at 9:01 PM Jann Horn <jannh@google.com> wrote:
> >
> > I don't understand what's going on here, unless you're saying that
> > Rust does not enforce that an object ownership transfer between
> > threads has proper RELEASE/ACQUIRE (or RELEASE/CONSUME) memory
> > ordering or something like that?
>
> Indeed without the Sync implementation, it does not make sense to have
> atomic ops that take &self.
> Sorry for the confusion, I should have added the Sync implementation.

Hang on, the Sync implementation is actually there in this patch! It
was missing previously.
Does that clarify things?

cheers,
Burak

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

[Jann Horn]

On Mon, May 19, 2025 at 10:08 PM Burak Emir <bqe@google.com> wrote:
> On Mon, May 19, 2025 at 9:01 PM Jann Horn <jannh@google.com> wrote:
> > On Mon, May 19, 2025 at 6:24 PM Burak Emir <bqe@google.com> wrote:
> > > +    /// Set bit with index `index`, atomically.
> > > +    ///
> > > +    /// ATTENTION: The naming convention differs from C, where the corresponding
> > > +    /// function is called `set_bit`.
> > > +    ///
> > > +    /// # Safety
> > > +    ///
> > > +    /// This is a relaxed atomic operation (no implied memory barriers, no
> > > +    /// ordering guarantees). The caller must ensure that this is safe, as
> > > +    /// the compiler cannot prevent code with an exclusive reference from
> > > +    /// calling atomic operations.
> >
> > How can atomic operations through an exclusive reference be unsafe?
> > You can't have a data race between two atomic operations, and an
> > exclusive reference should anyway prevent any concurrency, right?
>
> The atomic operations take a &self (shared reference).
>
> The patch is missing the implementation of Sync for now. With that,
> one would get concurrent write access through shared references.
>
> The "unsafe" here should serve as reminder to argue why it is ok to
> not have any ordering guarantees.
>
> The last sentence is supposed to say: when you have a &mut bitmap, you
> can reborrow it as &bitmap, and then happily call this atomic op.
> Even though it is unnecessary.

But using an atomic op when you have a &mut reference is not a safety
issue, right? You wrote a comment about behavior with exclusive
references in the "# Safety" comment block. If that's not supposed to
be a safety problem, this should probably not be in the "# Safety"
section?

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

[Burak Emir]

On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Mon, May 19, 2025 at 04:17:03PM +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:
> >
> >   * We leverage Rust type system guarantees as follows:
> >
> >     * Ownership transfer of a Bitmap is restricted so that it cannot
> >     be passed between threads (does not implement `Send`).
>
> Can you explain why you decided to not implement it? You can 'share' a
> reference, but prohibit 'sending' it...
>

My intention here was to be conservative. It seems safe to send a
Bitmap to a different thread,
in the sense that it would not cause data races.

Maybe it would be better to commit now to keep Bitmap "send"able - for all time.
It would however constrain the API quite a bit. One could never use this API
with a thread-local bitmap.

> >     * all (non-atomic) mutating operations require a &mut reference which
> >     amounts to exclusive access.
> >
> >     * It is permissible to pass shared references &Bitmap between
> >     threads, and we expose atomic operations through interior mutability.
> >     Since these atomic operations do not provide any ordering guarantees,
> >     we mark these as `unsafe`. Anyone who calls the atomic methods needs
> >     to document that the lack of ordering is safe.
> >
> >   * The Rust API offers `{set,clear}_bit` vs `{set,clear}_bit_atomic`,
> >     which is different from the C naming convention (set_bit vs __set_bit).
> >
> >   * we include enough operations for the API to be useful, but not all
> >     operations are exposed yet in order to avoid dead code. This commit
>
> This sentence and the following one say the same thing. Can you please
> rephrase?

Thanks for catching that, will do.

> >     includes enough to enable a Rust implementation of an Android Binder
> >     data structure that was introduced in commit 15d9da3f818c ("binder:
> >     use bitmap for faster descriptor lookup"), which can be found in
> >     drivers/android/dbitmap.h. We need this in order to upstream the Rust
> >     port of Android Binder driver.
> >
> >   * We follow the C API closely and fine-grained approach to safety:
> >
> >     * Low-level bit-ops methods get a safe API with bounds checks.
> >
> >     * methods correspond to find_* C methods tolerate out-of-bounds
> >     arguments. Since these are already safe we the same behavior, and
> >     return results using `Option` types to represent "not found".
>
> Nit: the above 2 lines look misaligned. Everywhere else you align
> items such that new lines under asterisk align with the first
> character, not the asterisk itself.

Yes, will fix.

> >
> >   * the Rust API is optimized to represent the bitmap inline if it would
> >     take the space of a pointer. This saves allocations which is
>
> s/take the space of/fits into/
>
> >     relevant in the Binder use case.
> >
> >   * Bounds checks where out-of-bounds values would not result in
> >     immediate access faults are configured via a RUST_BITMAP_HARDENED
> >     config.
> >
> > The underlying C bitmap is *not* exposed, and must never be exposed
> > (except in tests). Exposing the representation would lose all static
> > guarantees, and moreover would prevent the optimized representation of
> > short bitmaps.
>
> Does it mean that all existing kernel bitmaps declared in C are not
> accessible in Rust as well?

At the moment, we do not permit construction of a Rust Bitmap from an
existing C bitmap.
The point is more about the other direction though, not being able to
pass the Rust-owned bitmap to C code.

One could think of an API that requires an exclusively owned (no one
else has access) pointer to a C bitmap to Rust.
Though there is no general way to ensure that property, there are
situations where it would make sense (e.g. newly created).

> > 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, with the same performance
> > characteristics whenever possible.
>
> This should go in cover letter as well. Did you run any performance
> tests against the native bitmaps?

ok, I will mention it there. I have not run this against the Rust native bitmap.
I'd need to find out how to get a Rust native bitmap into kernel Rust code.

[...]

> > +    /// 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
> > +        );
>
> Shouldn't this assertion be protected with hardening too? I already
> said that: panicking on  out-of-boundary access with hardening
> disabled is a wrong way to go.

I considered it, but could not convince myself that __set_bit etc are
actually always safe.
For the methods that have the hardening assert, I was sure, but for
this one, not.

Are all bit ops guaranteed to handle out-of-bounds gracefully?

> Can you turn your bitmap_hardening_assert() to just bitmap_assert(),
> which panics only if hardening is enabled, and otherwise just prints
> error with pr_err()?

If there is no risk of undefined behavior, then I agree that checking
bounds is hardening.
If a missing bounds check loses safety, we then we should not skip it.

> Did you measure performance impact of hardening? Are those numbers in
> cover letter collected with hardening enabled or disabled? If
> performance impact is measurable, it should be mentioned in config
> description.

The hardening was enabled and it crossed my mind to mention it.
Given that not all methods have hardening, I though it might be misleading.

I'll have a more complete comparision and description in the next version.

[...]

> > +    /// Clear `index` bit, atomically.
> > +    ///
> > +    /// ATTENTION: The naming convention differs from C, where the corresponding
> > +    /// function is called `clear_bit`.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// This is a relaxed atomic operation (no implied memory barriers, no
> > +    /// ordering guarantees). The caller must ensure that this is safe, as
>
> Memory barriers is an implementation of 'ordering guarantees', so all
> this sounds tautology.
>

ok, i will remove one of them.

[...]
> > diff --git a/security/Kconfig.hardening b/security/Kconfig.hardening
> > index 3fe9d7b945c4..926665bbc8f2 100644
> > --- a/security/Kconfig.hardening
> > +++ b/security/Kconfig.hardening
> > @@ -324,6 +324,15 @@ config LIST_HARDENED
> >
> >         If unsure, say N.
> >
> > +config RUST_BITMAP_HARDENED
> > +     bool "Check integrity of linked list manipulation"
>
> Wah?

oh, thanks for catching that.

Thanks,
Burak

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

[Boqun Feng]

On Mon, May 19, 2025 at 10:36:52PM +0200, Jann Horn wrote:
> On Mon, May 19, 2025 at 10:08 PM Burak Emir <bqe@google.com> wrote:
> > On Mon, May 19, 2025 at 9:01 PM Jann Horn <jannh@google.com> wrote:
> > > On Mon, May 19, 2025 at 6:24 PM Burak Emir <bqe@google.com> wrote:
> > > > +    /// Set bit with index `index`, atomically.
> > > > +    ///
> > > > +    /// ATTENTION: The naming convention differs from C, where the corresponding
> > > > +    /// function is called `set_bit`.
> > > > +    ///
> > > > +    /// # Safety
> > > > +    ///
> > > > +    /// This is a relaxed atomic operation (no implied memory barriers, no
> > > > +    /// ordering guarantees). The caller must ensure that this is safe, as
> > > > +    /// the compiler cannot prevent code with an exclusive reference from
> > > > +    /// calling atomic operations.
> > >
> > > How can atomic operations through an exclusive reference be unsafe?
> > > You can't have a data race between two atomic operations, and an
> > > exclusive reference should anyway prevent any concurrency, right?
> >
> > The atomic operations take a &self (shared reference).
> >
> > The patch is missing the implementation of Sync for now. With that,
> > one would get concurrent write access through shared references.
> >
> > The "unsafe" here should serve as reminder to argue why it is ok to
> > not have any ordering guarantees.

I don't think ordering is safety related. For example, relaxed atomics
are still safe function. I think it's wrong to mark this as unsafe, do
you have an example that you can construct an UB with pure safe code?

Regards,
Boqun

> >
> > The last sentence is supposed to say: when you have a &mut bitmap, you
> > can reborrow it as &bitmap, and then happily call this atomic op.
> > Even though it is unnecessary.
> 
> But using an atomic op when you have a &mut reference is not a safety
> issue, right? You wrote a comment about behavior with exclusive
> references in the "# Safety" comment block. If that's not supposed to
> be a safety problem, this should probably not be in the "# Safety"
> section?

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

[Jann Horn]

On Mon, May 19, 2025 at 10:42 PM Burak Emir <bqe@google.com> wrote:
> On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.norov@gmail.com> wrote:
> > On Mon, May 19, 2025 at 04:17:03PM +0000, Burak Emir wrote:
> > > +    /// 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
> > > +        );
> >
> > Shouldn't this assertion be protected with hardening too? I already
> > said that: panicking on  out-of-boundary access with hardening
> > disabled is a wrong way to go.
>
> I considered it, but could not convince myself that __set_bit etc are
> actually always safe.
> For the methods that have the hardening assert, I was sure, but for
> this one, not.
>
> Are all bit ops guaranteed to handle out-of-bounds gracefully?
>
> > Can you turn your bitmap_hardening_assert() to just bitmap_assert(),
> > which panics only if hardening is enabled, and otherwise just prints
> > error with pr_err()?
>
> If there is no risk of undefined behavior, then I agree that checking
> bounds is hardening.
> If a missing bounds check loses safety, we then we should not skip it.

There are no bounds checks in these C APIs, and there can't be,
because the C side does not store a length. bitmap_zalloc() just gives
you a raw array of bits (represented in C as an array of unsigned
longs), it's a very lightweight wrapper around kmalloc_array().

And if you expand __set_bit(nr, addr), you'll see that it turns into:

bitop(___set_bit, nr, addr)

which turns into:

((__builtin_constant_p(nr) &&
  __builtin_constant_p((uintptr_t)(addr) != (uintptr_t)NULL) &&
  (uintptr_t)(addr) != (uintptr_t)NULL &&
  __builtin_constant_p(*(const unsigned long *)(addr))) ?
const___set_bit(nr, addr) : ___set_bit(nr, addr))

which (assuming a non-constant index) is:

___set_bit(nr, addr)

which is a debug-instrumented wrapper around

arch___set_bit(nr, addr)

which just leads to a raw assembly instruction (example from x86):

static __always_inline void
arch___set_bit(unsigned long nr, volatile unsigned long *addr)
{
    asm volatile(__ASM_SIZE(bts) " %1,%0" : : ADDR, "Ir" (nr) : "memory");
}

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

[Miguel Ojeda]

On Mon, May 19, 2025 at 10:08 PM Burak Emir <bqe@google.com> wrote:
>
> The "unsafe" here should serve as reminder to argue why it is ok to
> not have any ordering guarantees.

`unsafe` should be used for unsafe functions, not as a general
"danger" or "advanced" marker.

(Having such a marker could be useful, but `unsafe fn` is not it)

> The last sentence is supposed to say: when you have a &mut bitmap, you
> can reborrow it as &bitmap, and then happily call this atomic op.
> Even though it is unnecessary.

I don't think that is related to safety preconditions. A "# Safety"
section is intended to explain what the preconditions are.

So, for instance, stating "The caller must ensure that this is safe"
does not add much.

Cheers,
Miguel

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

[Burak Emir]

On Mon, May 19, 2025 at 11:42 PM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> On Mon, May 19, 2025 at 10:08 PM Burak Emir <bqe@google.com> wrote:
> >
> > The "unsafe" here should serve as reminder to argue why it is ok to
> > not have any ordering guarantees.
>
> `unsafe` should be used for unsafe functions, not as a general
> "danger" or "advanced" marker.
>
> (Having such a marker could be useful, but `unsafe fn` is not it)
>

I can see the appeal of having a strict definition "safe = no UB".

> > The last sentence is supposed to say: when you have a &mut bitmap, you
> > can reborrow it as &bitmap, and then happily call this atomic op.
> > Even though it is unnecessary.
>
> I don't think that is related to safety preconditions. A "# Safety"
> section is intended to explain what the preconditions are.
>
> So, for instance, stating "The caller must ensure that this is safe"
> does not add much.

I see what you are saying. Not being sensitive to order is a
precondition to a property.
There are many different kinds of (colloquial) safety e.g. crash
safety or data integrity.

Sticking to a technical definition of safety has the advantage that
one can be consistent.
So I'll remove the unsafe marker then.

Thanks,
- Burak

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

[Yury Norov]

On Mon, May 19, 2025 at 10:41:58PM +0200, Burak Emir wrote:
> On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.norov@gmail.com> wrote:
> >
> > On Mon, May 19, 2025 at 04:17:03PM +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:
> > >
> > >   * We leverage Rust type system guarantees as follows:
> > >
> > >     * Ownership transfer of a Bitmap is restricted so that it cannot
> > >     be passed between threads (does not implement `Send`).
> >
> > Can you explain why you decided to not implement it? You can 'share' a
> > reference, but prohibit 'sending' it...
> >
> 
> My intention here was to be conservative. It seems safe to send a
> Bitmap to a different thread,
> in the sense that it would not cause data races.
> 
> Maybe it would be better to commit now to keep Bitmap "send"able - for all time.
> It would however constrain the API quite a bit. One could never use this API
> with a thread-local bitmap.

I'd implement the Send method, or just say that the method is to be
implemented in future when it will be needed.
 
> > >     * all (non-atomic) mutating operations require a &mut reference which
> > >     amounts to exclusive access.
> > >
> > >     * It is permissible to pass shared references &Bitmap between
> > >     threads, and we expose atomic operations through interior mutability.
> > >     Since these atomic operations do not provide any ordering guarantees,
> > >     we mark these as `unsafe`. Anyone who calls the atomic methods needs
> > >     to document that the lack of ordering is safe.
> > >
> > >   * The Rust API offers `{set,clear}_bit` vs `{set,clear}_bit_atomic`,
> > >     which is different from the C naming convention (set_bit vs __set_bit).
> > >
> > >   * we include enough operations for the API to be useful, but not all
> > >     operations are exposed yet in order to avoid dead code. This commit
> >
> > This sentence and the following one say the same thing. Can you please
> > rephrase?
> 
> Thanks for catching that, will do.
> 
> > >     includes enough to enable a Rust implementation of an Android Binder
> > >     data structure that was introduced in commit 15d9da3f818c ("binder:
> > >     use bitmap for faster descriptor lookup"), which can be found in
> > >     drivers/android/dbitmap.h. We need this in order to upstream the Rust
> > >     port of Android Binder driver.
> > >
> > >   * We follow the C API closely and fine-grained approach to safety:
> > >
> > >     * Low-level bit-ops methods get a safe API with bounds checks.
> > >
> > >     * methods correspond to find_* C methods tolerate out-of-bounds
> > >     arguments. Since these are already safe we the same behavior, and
> > >     return results using `Option` types to represent "not found".
> >
> > Nit: the above 2 lines look misaligned. Everywhere else you align
> > items such that new lines under asterisk align with the first
> > character, not the asterisk itself.
> 
> Yes, will fix.
> 
> > >
> > >   * the Rust API is optimized to represent the bitmap inline if it would
> > >     take the space of a pointer. This saves allocations which is
> >
> > s/take the space of/fits into/
> >
> > >     relevant in the Binder use case.
> > >
> > >   * Bounds checks where out-of-bounds values would not result in
> > >     immediate access faults are configured via a RUST_BITMAP_HARDENED
> > >     config.
> > >
> > > The underlying C bitmap is *not* exposed, and must never be exposed
> > > (except in tests). Exposing the representation would lose all static
> > > guarantees, and moreover would prevent the optimized representation of
> > > short bitmaps.
> >
> > Does it mean that all existing kernel bitmaps declared in C are not
> > accessible in Rust as well?
> 
> At the moment, we do not permit construction of a Rust Bitmap from an
> existing C bitmap.
> The point is more about the other direction though, not being able to
> pass the Rust-owned bitmap to C code.
> 
> One could think of an API that requires an exclusively owned (no one
> else has access) pointer to a C bitmap to Rust.
> Though there is no general way to ensure that property, there are
> situations where it would make sense (e.g. newly created).

OK. Can you also mention it? And if we'll need to share bitmaps
between C and Rust modules, are you going to create a new class, or
extent the existing one?

> > > 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, with the same performance
> > > characteristics whenever possible.
> >
> > This should go in cover letter as well. Did you run any performance
> > tests against the native bitmaps?
> 
> ok, I will mention it there. I have not run this against the Rust native bitmap.
> I'd need to find out how to get a Rust native bitmap into kernel Rust code.
> 
> [...]
> 
> > > +    /// 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
> > > +        );
> >
> > Shouldn't this assertion be protected with hardening too? I already
> > said that: panicking on  out-of-boundary access with hardening
> > disabled is a wrong way to go.
> 
> I considered it, but could not convince myself that __set_bit etc are
> actually always safe.
> For the methods that have the hardening assert, I was sure, but for
> this one, not.
> 
> Are all bit ops guaranteed to handle out-of-bounds gracefully?

No. set_bit(), clear_bit() and test_bit() don't know the bitmap size
and can't check out-of-boundary. 

But your Rust set_bit() does! You can check boundaries unconditionally,
and throw errors depending on the hardening config. If user wants to set
an out-of-boundary bit, you should just do nothing,

> > Can you turn your bitmap_hardening_assert() to just bitmap_assert(),
> > which panics only if hardening is enabled, and otherwise just prints
> > error with pr_err()?
> 
> If there is no risk of undefined behavior, then I agree that checking
> bounds is hardening.
> If a missing bounds check loses safety, we then we should not skip it.
> 
> > Did you measure performance impact of hardening? Are those numbers in
> > cover letter collected with hardening enabled or disabled? If
> > performance impact is measurable, it should be mentioned in config
> > description.
> 
> The hardening was enabled and it crossed my mind to mention it.
> Given that not all methods have hardening, I though it might be misleading.
> 
> I'll have a more complete comparision and description in the next version.
 
The hardening should be disabled for benchmarking reasons, isn't?

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

[Jann Horn]

On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> This is a port of the Binder data structure introduced in commit
> 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> Rust.

Stupid high-level side comment:

That commit looks like it changed a simple linear rbtree scan (which
is O(n) with slow steps) into a bitmap thing. A more elegant option
might have been to use an augmented rbtree, reducing the O(n) rbtree
scan to an O(log n) rbtree lookup, just like how finding a free area
used to work in MM code... That would let you drop that ID pool bitmap
entirely. But I guess actually wiring up an augmented rbtree into Rust
would be very annoying too.

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

[Alice Ryhl]

On Mon, May 19, 2025 at 3:51 PM Jann Horn <jannh@google.com> wrote:
>
> On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > This is a port of the Binder data structure introduced in commit
> > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > Rust.
>
> Stupid high-level side comment:
>
> That commit looks like it changed a simple linear rbtree scan (which
> is O(n) with slow steps) into a bitmap thing. A more elegant option
> might have been to use an augmented rbtree, reducing the O(n) rbtree
> scan to an O(log n) rbtree lookup, just like how finding a free area
> used to work in MM code... That would let you drop that ID pool bitmap
> entirely. But I guess actually wiring up an augmented rbtree into Rust
> would be very annoying too.

If we're talking approaches to avoid the bitmap entirely, it would
probably be easier to replace the rb tree with xarray than to use an
augmented one.

Alice

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

[Jann Horn]

On Tue, May 20, 2025 at 1:12 AM Alice Ryhl <aliceryhl@google.com> wrote:
> On Mon, May 19, 2025 at 3:51 PM Jann Horn <jannh@google.com> wrote:
> > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > This is a port of the Binder data structure introduced in commit
> > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > Rust.
> >
> > Stupid high-level side comment:
> >
> > That commit looks like it changed a simple linear rbtree scan (which
> > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > scan to an O(log n) rbtree lookup, just like how finding a free area
> > used to work in MM code... That would let you drop that ID pool bitmap
> > entirely. But I guess actually wiring up an augmented rbtree into Rust
> > would be very annoying too.
>
> If we're talking approaches to avoid the bitmap entirely, it would
> probably be easier to replace the rb tree with xarray than to use an
> augmented one.

Ah, yeah, maybe. I'm not familiar enough with xarray to know how
annoying it would be to insert stuff in an xarray that you reach
through a spinlock, which seems to be the requirement that made the
API for the bitmap interface so complicated if I understand
correctly...

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

[Boqun Feng]

On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > This is a port of the Binder data structure introduced in commit
> > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > Rust.
> 
> Stupid high-level side comment:
> 
> That commit looks like it changed a simple linear rbtree scan (which
> is O(n) with slow steps) into a bitmap thing. A more elegant option
> might have been to use an augmented rbtree, reducing the O(n) rbtree
> scan to an O(log n) rbtree lookup, just like how finding a free area

I think RBTree::cursor_lower_bound() [1] does exactly what you said

[1]: https://rust.docs.kernel.org/kernel/rbtree/struct.RBTree.html#method.cursor_lower_bound

Regards,
Boqun

> used to work in MM code... That would let you drop that ID pool bitmap
> entirely. But I guess actually wiring up an augmented rbtree into Rust
> would be very annoying too.

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

[Yury Norov]

+ Carlos Llamas

On Mon, May 19, 2025 at 04:56:21PM -0700, Boqun Feng wrote:
> On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > This is a port of the Binder data structure introduced in commit
> > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > Rust.
> > 
> > Stupid high-level side comment:
> > 
> > That commit looks like it changed a simple linear rbtree scan (which
> > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > scan to an O(log n) rbtree lookup, just like how finding a free area
> 
> I think RBTree::cursor_lower_bound() [1] does exactly what you said
> 
> [1]: https://rust.docs.kernel.org/kernel/rbtree/struct.RBTree.html#method.cursor_lower_bound

Alice mentioned before that in many cases the whole pool of IDs will
fit into a single machine word if represented as bitmap. If that holds,
bitmaps will win over any other data structure that I can imagine. 

For very large ID pools, the algorithmic complexity will take over,
for sure. On the other hand, the 15d9da3f818ca explicitly mentions
that it switches implementation to bitmaps for performance reasons. 

Anyways, Burak and Alice, before we move forward, can you tell if you
ran any experiments with data structures allowing logarithmic lookup,
like rb-tree? Can you maybe measure at which point rb-tree lookup will
win over find_bit as the size of pool growth?

Can you describe how the existing dbitmap is used now? What is the
typical size of ID pools? Which operation is the bottleneck? Looking
forward, are there any expectations about ID pools size in future?

Carlos, can you please elaborate your motivation to switch to bitmaps?
Have you considered rb-trees with O(logn) lookup?

Thanks,
Yury

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

[Alice Ryhl]

On Mon, May 19, 2025 at 5:57 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> + Carlos Llamas
>
> On Mon, May 19, 2025 at 04:56:21PM -0700, Boqun Feng wrote:
> > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > This is a port of the Binder data structure introduced in commit
> > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > Rust.
> > >
> > > Stupid high-level side comment:
> > >
> > > That commit looks like it changed a simple linear rbtree scan (which
> > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > scan to an O(log n) rbtree lookup, just like how finding a free area
> >
> > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> >
> > [1]: https://rust.docs.kernel.org/kernel/rbtree/struct.RBTree.html#method.cursor_lower_bound
>
> Alice mentioned before that in many cases the whole pool of IDs will
> fit into a single machine word if represented as bitmap. If that holds,
> bitmaps will win over any other data structure that I can imagine.
>
> For very large ID pools, the algorithmic complexity will take over,
> for sure. On the other hand, the 15d9da3f818ca explicitly mentions
> that it switches implementation to bitmaps for performance reasons.
>
> Anyways, Burak and Alice, before we move forward, can you tell if you
> ran any experiments with data structures allowing logarithmic lookup,
> like rb-tree? Can you maybe measure at which point rb-tree lookup will
> win over find_bit as the size of pool growth?
>
> Can you describe how the existing dbitmap is used now? What is the
> typical size of ID pools? Which operation is the bottleneck? Looking
> forward, are there any expectations about ID pools size in future?

Generally, an Android phone will have around 3 processes with a large
ID pool (thousands of IDs), and essentially all other processes have a
very small number of IDs (less than 10). The large pools are typically
the same size as the number of concurrently running processes on the
device. The bitmap was added to the C driver to deal with perf issues
that came from doing linear lookups on the rbtree for the large pools
while holding a spinlock, and it did solve those perf issues.

Alice

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

[Alice Ryhl]

On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > This is a port of the Binder data structure introduced in commit
> > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > Rust.
> >
> > Stupid high-level side comment:
> >
> > That commit looks like it changed a simple linear rbtree scan (which
> > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > scan to an O(log n) rbtree lookup, just like how finding a free area
>
> I think RBTree::cursor_lower_bound() [1] does exactly what you said

We need the smallest ID without a value, not the smallest ID in use.

Alice

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

[Boqun Feng]

On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > This is a port of the Binder data structure introduced in commit
> > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > Rust.
> > >
> > > Stupid high-level side comment:
> > >
> > > That commit looks like it changed a simple linear rbtree scan (which
> > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > scan to an O(log n) rbtree lookup, just like how finding a free area
> >
> > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> 
> We need the smallest ID without a value, not the smallest ID in use.
> 

Ok, but it shouldn't be hard to write a Rust function that search that,
right? My point was mostly the Rust rbtree binding can do O(log n)
search. I have no idea about "even so, should we try something like Jann
suggested". And I think your other reply basically says no.

Regards,
Boqun

> Alice

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

[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 kees/for-next/hardening kees/for-next/pstore kees/for-next/kspp linus/master v6.15-rc7]
[cannot apply to next-20250516]
[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/20250520-002216
base:   https://github.com/Rust-for-Linux/linux rust-next
patch link:    https://lore.kernel.org/r/20250519161712.2609395-4-bqe%40google.com
patch subject: [PATCH v8 3/5] rust: add bitmap API.
config: x86_64-rhel-9.4-rust (https://download.01.org/0day-ci/archive/20250520/202505201339.bUfYKFye-lkp@intel.com/config)
compiler: clang version 18.1.8 (https://github.com/llvm/llvm-project 3b5b5c1ec4a3095ab096dd780e84d7ab81f3d7ff)
rustc: rustc 1.78.0 (9b00956e5 2024-04-29)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250520/202505201339.bUfYKFye-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/202505201339.bUfYKFye-lkp@intel.com/

All errors (new ones prefixed by >>):

>> error[E0061]: this method takes 0 arguments but 1 argument was supplied
   --> rust/kernel/bitmap.rs:396:28
   |
   396 |         assert_eq!(None, b.last_bit(2048));
   |                            ^^^^^^^^ ----
   |                                     |
   |                                     unexpected argument of type `{integer}`
   |                                     help: remove the extra argument
   |
   note: method defined here
   --> rust/kernel/bitmap.rs:301:12
   |
   301 |     pub fn last_bit(&self) -> Option<usize> {
   |            ^^^^^^^^

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

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

[Alice Ryhl]

On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > >
> > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > This is a port of the Binder data structure introduced in commit
> > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > Rust.
> > > >
> > > > Stupid high-level side comment:
> > > >
> > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > >
> > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> >
> > We need the smallest ID without a value, not the smallest ID in use.
> >
>
> Ok, but it shouldn't be hard to write a Rust function that search that,
> right? My point was mostly the Rust rbtree binding can do O(log n)
> search. I have no idea about "even so, should we try something like Jann
> suggested". And I think your other reply basically says no.

We would need to store additional data in the r/b tree to know whether
to go left or right, so it would be somewhat tricky. We don't have an
implementation of that in Rust.

Alice

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

[Boqun Feng]

On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > Rust.
> > > > >
> > > > > Stupid high-level side comment:
> > > > >
> > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > >
> > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > >
> > > We need the smallest ID without a value, not the smallest ID in use.
> > >
> >
> > Ok, but it shouldn't be hard to write a Rust function that search that,
> > right? My point was mostly the Rust rbtree binding can do O(log n)
> > search. I have no idea about "even so, should we try something like Jann
> > suggested". And I think your other reply basically says no.
> 
> We would need to store additional data in the r/b tree to know whether
> to go left or right, so it would be somewhat tricky. We don't have an

Hmm... I'm confused, I thought you can implement a search like that by
doing what RBTree::raw_entry() does except that when Ordering::Equal you
always go left or right (depending on whether you want to get an unused
ID less or greater than a key value), i.e. you always search until you
get an Vacant entry. Why do you need store additional data for that?
Maybe I'm missing something here?

Regards,
Boqun

> implementation of that in Rust.
> 
> Alice

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

[Alice Ryhl]

On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > >
> > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > >
> > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > > Rust.
> > > > > >
> > > > > > Stupid high-level side comment:
> > > > > >
> > > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > > >
> > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > >
> > > > We need the smallest ID without a value, not the smallest ID in use.
> > > >
> > >
> > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > search. I have no idea about "even so, should we try something like Jann
> > > suggested". And I think your other reply basically says no.
> >
> > We would need to store additional data in the r/b tree to know whether
> > to go left or right, so it would be somewhat tricky. We don't have an
>
> Hmm... I'm confused, I thought you can implement a search like that by
> doing what RBTree::raw_entry() does except that when Ordering::Equal you
> always go left or right (depending on whether you want to get an unused
> ID less or greater than a key value), i.e. you always search until you
> get an Vacant entry. Why do you need store additional data for that?
> Maybe I'm missing something here?

Let's say you're at the root node of an r/b tree, and you see that the
root node has id 17, the left node has id 8, and the right node has id
25. Do you go left or right?

Alice

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

[Boqun Feng]

On Tue, May 20, 2025 at 06:05:52AM -0700, Alice Ryhl wrote:
> On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> >
> > On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > >
> > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > > > Rust.
> > > > > > >
> > > > > > > Stupid high-level side comment:
> > > > > > >
> > > > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > > > >
> > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > > >
> > > > > We need the smallest ID without a value, not the smallest ID in use.
> > > > >
> > > >
> > > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > > search. I have no idea about "even so, should we try something like Jann
> > > > suggested". And I think your other reply basically says no.
> > >
> > > We would need to store additional data in the r/b tree to know whether
> > > to go left or right, so it would be somewhat tricky. We don't have an
> >
> > Hmm... I'm confused, I thought you can implement a search like that by
> > doing what RBTree::raw_entry() does except that when Ordering::Equal you
> > always go left or right (depending on whether you want to get an unused
> > ID less or greater than a key value), i.e. you always search until you
> > get an Vacant entry. Why do you need store additional data for that?
> > Maybe I'm missing something here?
> 
> Let's say you're at the root node of an r/b tree, and you see that the
> root node has id 17, the left node has id 8, and the right node has id
> 25. Do you go left or right?
> 

I went to check what commit 15d9da3f818c actually did and I understand
what you mean now ;-) In your case, the rbtree cannot have nodes with
the same key. If Jann can provide the O(log n) search that could help in
this case, I'm happy to learn about it ;-)

Regards,
Boqun

> Alice

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

[Jann Horn]

On Tue, May 20, 2025 at 3:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> On Tue, May 20, 2025 at 06:05:52AM -0700, Alice Ryhl wrote:
> > On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > >
> > > On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > > > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > >
> > > > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > > >
> > > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > > > > Rust.
> > > > > > > >
> > > > > > > > Stupid high-level side comment:
> > > > > > > >
> > > > > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > > > > >
> > > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > > > >
> > > > > > We need the smallest ID without a value, not the smallest ID in use.
> > > > > >
> > > > >
> > > > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > > > search. I have no idea about "even so, should we try something like Jann
> > > > > suggested". And I think your other reply basically says no.
> > > >
> > > > We would need to store additional data in the r/b tree to know whether
> > > > to go left or right, so it would be somewhat tricky. We don't have an
> > >
> > > Hmm... I'm confused, I thought you can implement a search like that by
> > > doing what RBTree::raw_entry() does except that when Ordering::Equal you
> > > always go left or right (depending on whether you want to get an unused
> > > ID less or greater than a key value), i.e. you always search until you
> > > get an Vacant entry. Why do you need store additional data for that?
> > > Maybe I'm missing something here?
> >
> > Let's say you're at the root node of an r/b tree, and you see that the
> > root node has id 17, the left node has id 8, and the right node has id
> > 25. Do you go left or right?
> >
>
> I went to check what commit 15d9da3f818c actually did and I understand
> what you mean now ;-) In your case, the rbtree cannot have nodes with
> the same key. If Jann can provide the O(log n) search that could help in
> this case, I'm happy to learn about it ;-)

Linux has the concept of an "augmented rbtree", where you can stuff
extra information into the rbtree to keep track of things like "how
big is the biggest gap between objects in this subtree". This is how
the MM subsystem used to find free space in the virtual address space
before the maple tree refactor, a complicated example is here:

finding a free region (by looking at vm_area_struct::rb_subtree_gap to
decide whether to go left or right; this is made complicated here
because they have more search constraints):
https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L1841

But that requires an "augmented rbtree" where the rbtree code calls
back into callbacks for updating the subtree gap; the MM code has its
gap update here:
https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L261

And associates that with VMA trees through this macro magic that would
probably be a terrible fit for Rust code:
https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L400

As Alice said, this is probably not a great fit for Rust code. As she
said, an xarray or maple tree would have this kind of gap search
built-in, which would be nicer here. But if you're trying to do
insertions while holding your own outer spinlocks, I think they would
be hard (or impossible?) to use.

If you managed to avoid broad use of spinlocks, that might make it
much easier to use xarrays or maple trees (and that would also allow
you to make the bitmap API much simpler).

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

[Boqun Feng]

On Tue, May 20, 2025 at 05:55:47PM +0200, Jann Horn wrote:
> On Tue, May 20, 2025 at 3:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > On Tue, May 20, 2025 at 06:05:52AM -0700, Alice Ryhl wrote:
> > > On Tue, May 20, 2025 at 5:56 AM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > >
> > > > On Tue, May 20, 2025 at 05:42:51AM -0700, Alice Ryhl wrote:
> > > > > On Mon, May 19, 2025 at 10:21 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > >
> > > > > > On Mon, May 19, 2025 at 08:46:37PM -0700, Alice Ryhl wrote:
> > > > > > > On Mon, May 19, 2025 at 4:56 PM Boqun Feng <boqun.feng@gmail.com> wrote:
> > > > > > > >
> > > > > > > > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > > > > > > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > > > > > > > This is a port of the Binder data structure introduced in commit
> > > > > > > > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > > > > > > > Rust.
> > > > > > > > >
> > > > > > > > > Stupid high-level side comment:
> > > > > > > > >
> > > > > > > > > That commit looks like it changed a simple linear rbtree scan (which
> > > > > > > > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > > > > > > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > > > > > > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > > > > > > >
> > > > > > > > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > > > > > >
> > > > > > > We need the smallest ID without a value, not the smallest ID in use.
> > > > > > >
> > > > > >
> > > > > > Ok, but it shouldn't be hard to write a Rust function that search that,
> > > > > > right? My point was mostly the Rust rbtree binding can do O(log n)
> > > > > > search. I have no idea about "even so, should we try something like Jann
> > > > > > suggested". And I think your other reply basically says no.
> > > > >
> > > > > We would need to store additional data in the r/b tree to know whether
> > > > > to go left or right, so it would be somewhat tricky. We don't have an
> > > >
> > > > Hmm... I'm confused, I thought you can implement a search like that by
> > > > doing what RBTree::raw_entry() does except that when Ordering::Equal you
> > > > always go left or right (depending on whether you want to get an unused
> > > > ID less or greater than a key value), i.e. you always search until you
> > > > get an Vacant entry. Why do you need store additional data for that?
> > > > Maybe I'm missing something here?
> > >
> > > Let's say you're at the root node of an r/b tree, and you see that the
> > > root node has id 17, the left node has id 8, and the right node has id
> > > 25. Do you go left or right?
> > >
> >
> > I went to check what commit 15d9da3f818c actually did and I understand
> > what you mean now ;-) In your case, the rbtree cannot have nodes with
> > the same key. If Jann can provide the O(log n) search that could help in
> > this case, I'm happy to learn about it ;-)
> 
> Linux has the concept of an "augmented rbtree", where you can stuff
> extra information into the rbtree to keep track of things like "how
> big is the biggest gap between objects in this subtree". This is how
> the MM subsystem used to find free space in the virtual address space
> before the maple tree refactor, a complicated example is here:
> 
> finding a free region (by looking at vm_area_struct::rb_subtree_gap to
> decide whether to go left or right; this is made complicated here
> because they have more search constraints):
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L1841
> 
> But that requires an "augmented rbtree" where the rbtree code calls
> back into callbacks for updating the subtree gap; the MM code has its
> gap update here:
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L261
> 

I see. I was missing this part.

> And associates that with VMA trees through this macro magic that would
> probably be a terrible fit for Rust code:
> https://elixir.bootlin.com/linux/v4.19.325/source/mm/mmap.c#L400
> 

Well, not sure that's true implementation-wise, I mean it's just
function callbacks while you insert or erase nodes from rbtree, which
could probably be described by a trait like:

    pub trait RBTreeAugmented<K, V> {
        fn compute(node: &Node<K, V, Self>) -> Self;
    }

    impl<K, V> RBTreeAugmented<K, V> for () {
        fn compute(_node: &Node<K, V, Self>) -> Self {
	    ()
	}
    }
and we change the Node type into:

    pub struct Node<K, V, A: RBTreeAugmented<K, V> = ()> 
    {
        links: bindings::rb_node,
        key: K,
        value: V,
	augmented: A
    }

and _propagate() can be something like:

   unsafe fn augmented_propagate<K, V, A: RBTreeAugmented<K, V>>(
       mut node: *mut rb_node, stop: *mut rb_node
   ) {
       	while !ptr::eq(node, stop) {
            let rbnode = unsafe { container_of!(node, Node<K, V, A>, links) }.cast_mut();
	    let rbnode: &mut Node<K,V,A> = unsafe { &mut *rbnode };

	    let new_augmented = A::compute(rbnode);

	    if rbnode.aurmented == new_augmented {
	        break;
	    }
		if (node->rbaugmented == augmented)			\
			break;						\
	    rbnode.augmented = augmented;				\

	    node = rb_parent(node);
	}
   }

probably works? However I guess we don't need to do that right now given
Alice's point on xarray or maple tree.

Regards,
Boqun

> As Alice said, this is probably not a great fit for Rust code. As she
> said, an xarray or maple tree would have this kind of gap search
> built-in, which would be nicer here. But if you're trying to do
> insertions while holding your own outer spinlocks, I think they would
> be hard (or impossible?) to use.
> 
> If you managed to avoid broad use of spinlocks, that might make it
> much easier to use xarrays or maple trees (and that would also allow
> you to make the bitmap API much simpler).

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

[Jann Horn]

On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> +/// 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)
> +///       }
> +///     }
> +///   }
> +/// }
> +/// ```

Hmm, I think I just understood a bit better than before what's
actually going on in the C binder code... the reason why you have this
complicated API for reallocation here in Rust is that you want the
guarded_pool to not have its own lock, but a lock provided by the
caller? And so pool functions are unable to take/drop the lock that
protects the pool?

This is just me idly wondering, and I know I tend to come up with
overcomplicated approaches and I'm bad at Rust - please just ignore
this message if you think it's not a good idea.

I wonder if there is a way in Rust to address this kind of situation
that looks nicer. Maybe you could have a function as part of the
IdPool implementation that operates on an IdPool, but instead of an
IdPool as parameter, the parameter is something like a function that
can be called to obtain a guard that gives you a mutable reference?
Could you maybe have some lock trait whose implementations store a
pointer to something like a SpinLock, with a "lock()" method that
first locks the SpinLock (creating a Guard), then looks up a specific
member of the data contained inside the SpinLock, and returns a
mutable pointer to that? Basically a subset view of the SpinLock. Then
the IdPool implementation would be able to internally do this pattern
of alternating lock/unlock. Though this way you'd still have to not
hold the lock when calling into this.

It might be an even better fit for a 1:1 translation of the C code if
you could then combine this with some kind of SpinLockUnlockGuard that
mutably borrows a SpinLockGuard; releases the underlying lock when it
is created; and reacquires the lock when it is dropped... but that's
maybe taking things too far.

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

[Carlos Llamas]

On Mon, May 19, 2025 at 08:57:04PM -0400, Yury Norov wrote:
> + Carlos Llamas
> 
> On Mon, May 19, 2025 at 04:56:21PM -0700, Boqun Feng wrote:
> > On Tue, May 20, 2025 at 12:51:07AM +0200, Jann Horn wrote:
> > > On Mon, May 19, 2025 at 6:20 PM Burak Emir <bqe@google.com> wrote:
> > > > This is a port of the Binder data structure introduced in commit
> > > > 15d9da3f818c ("binder: use bitmap for faster descriptor lookup") to
> > > > Rust.
> > > 
> > > Stupid high-level side comment:
> > > 
> > > That commit looks like it changed a simple linear rbtree scan (which
> > > is O(n) with slow steps) into a bitmap thing. A more elegant option
> > > might have been to use an augmented rbtree, reducing the O(n) rbtree
> > > scan to an O(log n) rbtree lookup, just like how finding a free area
> > 
> > I think RBTree::cursor_lower_bound() [1] does exactly what you said
> > 
> > [1]: https://rust.docs.kernel.org/kernel/rbtree/struct.RBTree.html#method.cursor_lower_bound
> 
> Alice mentioned before that in many cases the whole pool of IDs will
> fit into a single machine word if represented as bitmap. If that holds,
> bitmaps will win over any other data structure that I can imagine. 
> 
> For very large ID pools, the algorithmic complexity will take over,
> for sure. On the other hand, the 15d9da3f818ca explicitly mentions
> that it switches implementation to bitmaps for performance reasons. 
> 
> Anyways, Burak and Alice, before we move forward, can you tell if you
> ran any experiments with data structures allowing logarithmic lookup,
> like rb-tree? Can you maybe measure at which point rb-tree lookup will
> win over find_bit as the size of pool growth?
> 
> Can you describe how the existing dbitmap is used now? What is the
> typical size of ID pools? Which operation is the bottleneck? Looking
> forward, are there any expectations about ID pools size in future?
> 
> Carlos, can you please elaborate your motivation to switch to bitmaps?
> Have you considered rb-trees with O(logn) lookup?

Yeah, we tried rb-trees. There was even a patch that implemented the
augmented logic. See this:
https://lore.kernel.org/all/20240917030203.286-1-ebpqwerty472123@gmail.com/
IIRC, it just didn't make sense for our use case because of the extra
memory bytes required for this solution. The performance ended up being
the same (from my local testing).

I'm not certain of this but one potential factor is that the rb nodes
are in-strucutre members allocated separately. This can lead to more
cache misses when traversing them. I don't know how applicable this
would be for the Rust implementation though. Take that with a grain of
salt as I didn't actually look super close while running the tests.

I would also note, this whole logic wouldn't be required if userspace
wasn't using these descriptor IDs as vector indexes. At some point this
practice will be fixed and we can remove the "dbitmap" implementation.

Cheers,
--
Carlos Llamas

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

[Yury Norov]

On Wed, May 21, 2025 at 03:57:55AM +0000, Carlos Llamas wrote:
> On Mon, May 19, 2025 at 08:57:04PM -0400, Yury Norov wrote:
> > + Carlos Llamas

...

> > Carlos, can you please elaborate your motivation to switch to bitmaps?
> > Have you considered rb-trees with O(logn) lookup?
> 
> Yeah, we tried rb-trees. There was even a patch that implemented the
> augmented logic. See this:
> https://lore.kernel.org/all/20240917030203.286-1-ebpqwerty472123@gmail.com/
> IIRC, it just didn't make sense for our use case because of the extra
> memory bytes required for this solution. The performance ended up being
> the same (from my local testing).
> 
> I'm not certain of this but one potential factor is that the rb nodes
> are in-strucutre members allocated separately. This can lead to more
> cache misses when traversing them. I don't know how applicable this
> would be for the Rust implementation though. Take that with a grain of
> salt as I didn't actually look super close while running the tests.
> 
> I would also note, this whole logic wouldn't be required if userspace
> wasn't using these descriptor IDs as vector indexes. At some point this
> practice will be fixed and we can remove the "dbitmap" implementation.

Yeah, I expected to get this kind of feedback from real-world testing.
Your reply to the patch you mentioned above answers all my questions:

https://lore.kernel.org/all/ZwdWe_I2p3zD-v1O@google.com/

Let's stick to bitmaps unless someone shows clear benefit of using any
alternative approach, both in time and memory perspectives, supported
by testing.

Thanks,
Yury

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

[Burak Emir]

On Wed, May 21, 2025 at 3:50 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Wed, May 21, 2025 at 03:57:55AM +0000, Carlos Llamas wrote:
> > On Mon, May 19, 2025 at 08:57:04PM -0400, Yury Norov wrote:
> > > + Carlos Llamas
>
> ...
>
> > > Carlos, can you please elaborate your motivation to switch to bitmaps?
> > > Have you considered rb-trees with O(logn) lookup?
> >
> > Yeah, we tried rb-trees. There was even a patch that implemented the
> > augmented logic. See this:
> > https://lore.kernel.org/all/20240917030203.286-1-ebpqwerty472123@gmail.com/
> > IIRC, it just didn't make sense for our use case because of the extra
> > memory bytes required for this solution. The performance ended up being
> > the same (from my local testing).
> >
> > I'm not certain of this but one potential factor is that the rb nodes
> > are in-strucutre members allocated separately. This can lead to more
> > cache misses when traversing them. I don't know how applicable this
> > would be for the Rust implementation though. Take that with a grain of
> > salt as I didn't actually look super close while running the tests.
> >
> > I would also note, this whole logic wouldn't be required if userspace
> > wasn't using these descriptor IDs as vector indexes. At some point this
> > practice will be fixed and we can remove the "dbitmap" implementation.
>
> Yeah, I expected to get this kind of feedback from real-world testing.
> Your reply to the patch you mentioned above answers all my questions:
>
> https://lore.kernel.org/all/ZwdWe_I2p3zD-v1O@google.com/
>
> Let's stick to bitmaps unless someone shows clear benefit of using any
> alternative approach, both in time and memory perspectives, supported
> by testing.

Thanks all for the additional context.

Yury, I've addressed most of the comments.

You also commented on the API. The weirdness of the API is all due to
the separating "request to shrink/grow" from allocation.
Since allocation can happen while other threads may mess with the id
pool, one has to double check that the request to shrink/grow still
makes sense.
Dealing with this situation is required in the Android binder context
where this ID pool is used, my understanding is that one cannot
allocate there while holding the spinlock.

In the next version, I have renamed the operations to make this a bit
clearer, and made the comments a bit more explicit.
If it's ok, let's move the discussion to v9 that I will send in a
moment, I hope it clears things up a bit.

Thanks.
Burak