Message-ID: <aDXLqJTWlsrvVYB2@yury>
Date: Tue, 27 May 2025 10:27:01 -0400
From: Yury Norov <yury.norov@...il.com>
To: Burak Emir <bqe@...gle.com>
Cc: Kees Cook <kees@...nel.org>,
	Rasmus Villemoes <linux@...musvillemoes.dk>,
	Viresh Kumar <viresh.kumar@...aro.org>,
	Miguel Ojeda <ojeda@...nel.org>,
	Alex Gaynor <alex.gaynor@...il.com>,
	Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>,
	Björn Roy Baron <bjorn3_gh@...tonmail.com>,
	Benno Lossin <benno.lossin@...ton.me>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Alice Ryhl <aliceryhl@...gle.com>, Trevor Gross <tmgross@...ch.edu>,
	"Gustavo A . R . Silva" <gustavoars@...nel.org>,
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org,
	linux-hardening@...r.kernel.org
Subject: Re: [PATCH v9 0/5] rust: adds Bitmap API, ID pool and bindings

On Mon, May 26, 2025 at 03:01:29PM +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.
> 
> We ran a simple benchmark (sample size 32), with RUST_BITMAP_HARDENED=n
> on a x86_64 production machine that was not running other processes.
> 
> Results for random-filled bitmap:
> +------------+------+-----------+--------------+-----------+-----------+
> | Benchmark  | Code | Mean (ns) | Std Dev (ns) | 95% CI Lo | 95% CI Hi |
> +------------+------+-----------+--------------+-----------+-----------+
> | find_bit/  | C    |      5.18 |         0.32 |      5.17 |      5.18 |
> | next_bit   | Rust |      5.30 |         0.37 |      5.30 |      5.31 |
> +------------+------+-----------+--------------+-----------+-----------+
> | find_zero/ | C    |      5.66 |         0.33 |      5.66 |      5.67 |
> | next_zero  | Rust |      5.88 |         0.32 |      5.88 |      5.89 |
> +------------+------+-----------+--------------+-----------+-----------+

So, 95% CI means z=1.96, isn't? And to me it should be, for example for
the first line: 5.18 +- 1.96*0.32/sqrt(32) = 5.18 +- 0.11 = [5.07, 5.29].
Can you check your math please?
 
> Results for sparse bitmap:
> +------------+------+-----------+--------------+-----------+-----------+
> | Benchmark  | Code | Mean (ns) | Std Dev (ns) | 95% CI Lo | 95% CI Hi |
> +------------+------+-----------+--------------+-----------+-----------+
> | find_bit/  | C    |     22.51 |        12.34 |     22.38 |     22.65 |
> | next_bit   | Rust |     30.53 |        20.44 |     30.30 |     30.75 |
> +------------+------+-----------+--------------+-----------+-----------+
> | find_zero/ | C    |      5.69 |         0.22 |      5.68 |      5.69 |
> | next_zero  | Rust |      5.68 |         0.29 |      5.68 |      5.68 |
> +------------+------+-----------+--------------+-----------+-----------+

Your numbers look pretty weird. I wrote the test such that on a typical
x86 system it takes milliseconds for each subtest to pass.  Here you
report nanoseconds-scaled times. Did you divide by the number of
iterations? If so, please mention it.

Please print raw output of your test in patch #4 which adds the test.
Because the test is tightly coupled to it's C version, we need to make
sure it hast the same format - fields alignment, etc.

I would prefer to have detailed performance discussion in the
corresponding patch (#4), and here in cover letter you'd just mention
the overall performance difference - 2%, as I can see.

> 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 v9 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 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 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 [v8] https://lore.kernel.org/rust-for-linux/20250519161712.2609395-1-bqe@google.com/
> 
> Burak Emir (6):
>   rust: add bindings for bitmap.h
>   rust: add bindings for bitops.h
>   rust: add bitmap API.
>   bitmap: fix find_bit_benchmark module name and config description
>   rust: add find_bit_benchmark_rust module.
>   rust: add dynamic ID pool abstraction for bitmap
> 
>  MAINTAINERS                     |  15 ++
>  lib/Kconfig.debug               |  18 +-
>  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      |  11 +
>  12 files changed, 805 insertions(+), 2 deletions(-)
>  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
> 
> 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           | 568 ++++++++++++++++++++++++++++++++
>  rust/kernel/id_pool.rs          | 222 +++++++++++++
>  rust/kernel/lib.rs              |   2 +
>  security/Kconfig.hardening      |  10 +
>  12 files changed, 961 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.1151.ga128411c76-goog

Powered by blists - more mailing lists