Re: [PATCH v8 0/5] rust: adds Bitmap API, ID pool and bindings
From: Yury Norov
Date: Mon May 19 2025 - 14:34:56 EST
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@xxxxxxxxx/
> Link [2] https://lore.kernel.org/rust-for-linux/cover.1742296835.git.viresh.kumar@xxxxxxxxxx/
> Link [v7] https://lore.kernel.org/rust-for-linux/20250423134344.3888205-2-bqe@xxxxxxxxxx/
>
>
>
> 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