On Mon, Sep 08, 2025 at 07:21:50AM +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 series includes an optimization to represent the bitmap inline,
> as suggested by Yury.
>
> We ran a simple microbenchmark which shows that overall the Rust API
> can be expected to be about 4.5% slower than C API.
>
> We also introduce a Rust API in id_pool.rs that would replace
> dbitmap.h from the commit referenced above. This data structure is coupled
> with the bitmap API and adds support for growing and shrinking, along
> with fine-grained control over when allocation happens.
> The Binder code needs this since it holds a spinlock at the time it
> discovers that growing is necessary; this has to be release
> for performing a memory allocation with GFP_KERNEL that may cause
> sleep. We include example doctests that demonstrate this usage.
>
> Thanks everyone for all the helpful comments, this series has improved
> significantly as a result of your work.
>
> Changes v15 --> v16:
> - Rebased on commit 6ab41fca2e80 ("Merge tag 'timers-urgent-2025-09-07' of
> git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip")
> - kunit [test]s in Rust don't yet work with cfg, which breaks when
> CONFIG_RUST_BITMAP_HARDENED=y. Miguel identified the issue and
> suggested to move the [cfg] to body. Should be changed back when issue
> https://github.com/Rust-for-Linux/linux/issues/1185 is fixed.
>
> Changes v14 --> v15:
> - Rebased on commit 08b06c30a445 ("Merge tag 'v6.17-rc4-ksmbd-fix' of
> git://git.samba.org/ksmbd")
>
> Changes v13 --> v14:
> - Rebased on commit 8742b2d8935f ("Merge tag 'pull-fixes' of
> git://git.kernel.org/pub/scm/linux/kernel/git/viro/vfs")
> - applied clippy suggestions for pointer casts
> - in benchmark module, replace use of the Rust Ktime abstraction
> - in benchmark module, move newlines around for pr_cont to work
> with Instant, elapsed.
> - added Alice's Reviewed-by tag
>
> Changes v12 --> v13:
> - Rebased on commit 75f5f23f8787 ("Merge tag 'block-6.16-20250619' of
> git://git.kernel.dk/linux")
> - Renamed types CBitmap --> Bitmap, Bitmap --> BitmapVec.
> - Rewrote unit tests to not use `unwrap()` but `Result` and `?`
> - Replaced NonNull::as_mut() with NonNull::as_ptr()
> - declared local BITS_PER_LONG usize constants, fixed rustdoc
>
> Changes v11 --> v12:
> - Added Reviewed-by tag, changed named of benchmark module
> - Fixed config, rustdoc, clippy and bytes computation (Pekka).
> - Added test that exercises CONFIG_RUST_BITMAP_HARDENED,
> verified it panics.
> - Had to add a break to benchmark module, for the
> CONFIG_RUST_BITMAP_HARDENED case which enforces bounds check.
>
> Changes v10 --> v11:
> - Fix Kconfig dependency, Rust benchmark depends on CONFIG_RUST
> - Disable clippy warning for len() without is_empty() in id_pool.rs
>
> Changes v9 --> v10:
> - change helper to use `unsigned long` for `nr` parameter (Boqun)
> - add missing and fix safety comments (Boqun, Pekka)
> - move benchmark module output and results to #4 commit msg.
> - use pr_cont to avoid repeating find_bit_benchmark_rust log prefix.
> - Disable clippy warning for len() without is_empty() in bitmap.rs
>
> Changes v8 --> v9:
> - added a new type `CBitmap` that makes any C bitmap accessible with
> the same API, and add Deref so both Bitmap and
> CBitmap can share the same implementation. Full credit for this
> goes to Alice who suggested idea and code.
> - added config dependency on CONFIG_RUST that was missing from
> CONIG_FIND_BIT_BENCHMARK_RUST.
> - implemented Send for Bitmap, it is actually needed by Binder.
> - reworded commit msg for clarity.
> - removed unsafe for atomic ops.
> - renamed `bitmap_hardening_assert` to `bitmap_assert` and make operations
> do nothing and log error when RUST_BITMAP_HARDENED is off.
> - update author information in find_bit_benchmark_rust.rs
> - Various improvements to id_pool, better names and comments.
>
> Changes v7 --> v8:
> - added Acked-by for bindings patches
> - add RUST_BITMAP_HARDENED config, making 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/[email protected]/
> Link [2]
> https://lore.kernel.org/rust-for-linux/[email protected]/
> Link [v15]
> https://lore.kernel.org/rust-for-linux/[email protected]/
Added in bitmap-for-next for testing. Thanks.
