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

[Yury Norov <yury.norov@gmail.com>]

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