Message-ID: <LGWNtyhjCByj6PPHMsGCwo-WBkCCUuCOn_cUuwlwHPhfRZ4TdDR97a3u63ACSIvJQZF2SyAInyX90iMkERX2MK3Up-R6jazWHWhFzTIWah4=@protonmail.com>
Date: Thu, 05 Jun 2025 21:20:09 +0000
From: Pekka Ristola <pekkarr@...tonmail.com>
To: Burak Emir <bqe@...gle.com>
Cc: Yury Norov <yury.norov@...il.com>, 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>, Carlos LLama <cmllamas@...gle.com>, rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org, linux-hardening@...r.kernel.org
Subject: Re: [PATCH v11 3/5] rust: add bitmap API.

On Monday, June 2nd, 2025 at 16.53, Burak Emir <bqe@...gle.com> 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 <aliceryhl@...gle.com>
> Suggested-by: Yury Norov <yury.norov@...il.com>
> Signed-off-by: Burak Emir <bqe@...gle.com>
> ---
>  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 <aliceryhl@...gle.com>
> +M:	Burak Emir <bqe@...gle.com>
> +R:	Yury Norov <yury.norov@...il.com>
> +S:	Maintained
> +F:	rust/kernel/bitmap.rs
> +
>  BITOPS API
>  M:	Yury Norov <yury.norov@...il.com>
>  R:	Rasmus Villemoes <linux@...musvillemoes.dk>
> 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

Powered by blists - more mailing lists