On Monday, June 2nd, 2025 at 16.53, Burak Emir <[email protected]> wrote:
> Provides an abstraction for C bitmap API and bitops operations.
>
> This commit enables a Rust implementation of an Android Binder
> data structure from commit 15d9da3f818c ("binder: use bitmap for faster
> descriptor lookup"), which can be found in drivers/android/dbitmap.h.
> It is a step towards upstreaming the Rust port of Android Binder driver.
>
> 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:
>
> * all (non-atomic) mutating operations require a &mut reference which
> amounts to exclusive access.
>
> * the Bitmap type implements Send. This enables transferring
> ownership between threads and is needed for Binder.
>
> * the Bitmap type implements Sync, which enables passing shared
> references &Bitmap between threads. Atomic operations can be
> used to safely modify from multiple threads (interior
> mutability), though without ordering guarantees.
>
> * The Rust API uses `{set,clear}_bit` vs `{set,clear}_bit_atomic` as
> names, which differs from the C naming convention which uses
> set_bit for atomic vs __set_bit for non-atomic.
>
> * we include enough operations for the API to be useful, but not all
> operations are exposed yet in order to avoid dead code. The missing
> ones can be added later.
>
> * We follow the C API closely with a fine-grained approach to safety:
>
> * Low-level bit-ops get a safe API with bounds checks. Calling with
> an out-of-bounds arguments to {set,clear}_bit becomes a no-op and
> get logged as errors.
>
> * We introduce a RUST_BITMAP_HARDENED config, which
> causes invocations with out-of-bounds arguments to panic.
>
> * methods correspond to find_* C methods tolerate out-of-bounds
> since the C implementation does. Also here, we log out-of-bounds
> arguments as errors and panic in RUST_BITMAP_HARDENED mode.
>
> * We add a way to "borrow" bitmaps from C in Rust, to make C bitmaps
> that were allocated in C directly usable in Rust code (`CBitmap`).
>
> * the Rust API is optimized to represent the bitmap inline if it would
> fit into a pointer. This saves allocations which is
> relevant in the Binder use case.
>
> The underlying C bitmap is *not* exposed, and must never be exposed
> (except in tests). Exposing the representation of the owned bitmap would
> lose static guarantees.
>
> 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 <[email protected]>
> Suggested-by: Yury Norov <[email protected]>
> Signed-off-by: Burak Emir <[email protected]>
> ---
> MAINTAINERS | 7 +
> rust/kernel/bitmap.rs | 574 +++++++++++++++++++++++++++++++++++++
> rust/kernel/lib.rs | 1 +
> security/Kconfig.hardening | 10 +
> 4 files changed, 592 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 <[email protected]>
> +M: Burak Emir <[email protected]>
> +R: Yury Norov <[email protected]>
> +S: Maintained
> +F: rust/kernel/bitmap.rs
> +
> BITOPS API
> M: Yury Norov <[email protected]>
> R: Rasmus Villemoes <[email protected]>
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> new file mode 100644
> index 000000000000..28c11e400d1e
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,574 @@
[...]
> + /// Returns a raw pointer to the backing [`Bitmap`].
> + pub fn as_ptr(&self) -> *const usize {
> + self as *const CBitmap as *const usize
> + }
> +
> + /// Returns a mutable raw pointer to the backing [`Bitmap`].
> + pub fn as_mut_ptr(&mut self) -> *mut usize {
> + self as *mut CBitmap as *mut usize
> + }
> +
> + /// Returns length of this [`CBitmap`].
> + #[allow(clippy::len_without_is_empty)]
Using `expect` would be more idiomatic than `allow`.
> + pub fn len(&self) -> usize {
> + self.data.len()
> + }
> +}
> +
> +/// 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_assert {
> + ($cond:expr, $($arg:tt)+) => {
> + #[cfg(RUST_BITMAP_HARDENED)]
The config name should be prefixed with `CONFIG_`.
> + assert!($e, $($arg)*);
`$e` is not defined, it should be `$cond`.
> + }
> +}
> +
> +macro_rules! bitmap_assert_return {
> + ($cond:expr, $($arg:tt)+) => {
> + #[cfg(RUST_BITMAP_HARDENED)]
> + assert!($e, $($arg)*);
> +
> + #[cfg(not(RUST_BITMAP_HARDENED))]
> + if !($cond) {
> + pr_err!($($arg)*);
> + return
> + }
> + }
> +}
Same for this macro.
[...]
> + #[test]
> + fn bitmap_set_clear_find() {
> + let mut b = Bitmap::new(128, GFP_KERNEL).unwrap();
> +
> + // Zero-initialized
> + assert_eq!(None, b.next_bit(0));
> + assert_eq!(Some(0), b.next_zero_bit(0));
> + assert_eq!(None, b.last_bit());
> +
> + b.set_bit(17);
> +
> + assert_eq!(Some(17), b.next_bit(0));
> + assert_eq!(Some(17), b.next_bit(17));
> + assert_eq!(None, b.next_bit(18));
> + 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());
> + }
> +
> + #[cfg(not(RUST_BITMAP_HARDENED))]
Here as well, the config name should be `CONFIG_RUST_BITMAP_HARDENED`.
> + #[test]
> + fn bitmap_out_of_bounds() {
> + let mut b = Bitmap::new(128, GFP_KERNEL).unwrap();
> +
> + b.set_bit(2048);
> + b.set_bit_atomic(2048);
> + b.clear_bit(2048);
> + b.clear_bit_atomic(2048);
> + assert_eq!(None, b.next_bit(2048));
> + assert_eq!(None, b.next_zero_bit(2048));
> + assert_eq!(None, b.last_bit());
> + }
[...]
> diff --git a/security/Kconfig.hardening b/security/Kconfig.hardening
> index 3fe9d7b945c4..3ca3c7dc4381 100644
> --- a/security/Kconfig.hardening
> +++ b/security/Kconfig.hardening
> @@ -324,6 +324,16 @@ config LIST_HARDENED
>
> If unsure, say N.
>
> +config RUST_BITMAP_HARDENED
> + bool "Check integrity of linked list manipulation"
The description seems to have been copied from the previous menu entry.
> + depends on CONFIG_RUST
This needs to be `depends on RUST`, as Kconfig doesn't use the `CONFIG_`
prefix here.
> + 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.1204.g71687c7c1d-goog
Cheers,
Pekka
