Message-ID: <20250529193850.22210-1-pekkarr@protonmail.com>
Date: Thu, 29 May 2025 19:42: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>, rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org, linux-hardening@...r.kernel.org, Pekka Ristola <pekkarr@...tonmail.com>
Subject: Re: [PATCH v9 3/5] rust: add bitmap API.

On Mon, 26 May 2025 15:01:32 +0000, Burak Emir 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      | 554 +++++++++++++++++++++++++++++++++++++
>   rust/kernel/lib.rs         |   1 +
>   security/Kconfig.hardening |  10 +
>   4 files changed, 572 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..a6edd4889518
> --- /dev/null
> +++ b/rust/kernel/bitmap.rs
> @@ -0,0 +1,554 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +// Copyright (C) 2025 Google LLC.
> +
> +//! Rust API for bitmap.
> +//!
> +//! C headers: [`include/linux/bitmap.h`](srctree/include/linux/bitmap.h).
> +
> +use crate::alloc::{AllocError, Flags};
> +use crate::bindings;
> +use crate::pr_err;
> +use core::ptr::NonNull;
> +
> +/// Represents a C bitmap. Wraps underlying C bitmap API.
> +///
> +/// # Invariants
> +///
> +/// Must reference a `[c_ulong]` long enough to fit `data.len()` bits.
> +pub struct CBitmap {
> +    _align: [usize; 0],
> +    data: [()],

Interestingly, this zero sized slice layout seems to be fine under Tree
Borrows but UB under Stacked Borrows. This slightly modified version[0]
that runs in userspace triggers Miri with Stacked Borrows.

Though I guess it's fine since Miri doesn't complain with Tree Borrows.

[0] https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=0ccf6fd892c044db9b644a77ad9bd1e9

> +}
> +
> +impl CBitmap {
> +    /// Borrows a C bitmap.
> +    ///
> +    /// # Safety
> +    ///
> +    /// * `ptr` holds a non-null address of an initialized array of `unsigned long`
> +    ///   that is large enough to hold `nbits` bits.
> +    /// * the array must not be freed for the lifetime of this [`CBitmap`]
> +    /// * concurrent access only happens through atomic operations
> +    pub unsafe fn from_raw<'a>(ptr: *const usize, nbits: usize) -> &'a CBitmap {
> +        let data: *const [()] = core::ptr::slice_from_raw_parts(ptr.cast(), nbits);
> +        unsafe { &*(data as *const CBitmap) }

Safety comment is missing here. Running Clippy with `make LLVM=1 CLIPPY=1`
finds all the missing safety comments and some other issues as well.

[...]

> +/// 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)]
> +        assert!($e, $($arg)*);

Should be $cond instead of $e.

> +    }
> +}
> +
> +macro_rules! bitmap_assert_return {
> +    ($cond:expr, $($arg:tt)+) => {
> +        #[cfg(RUST_BITMAP_HARDENED)]
> +        assert!($e, $($arg)*);

Same here.

> +
> +        #[cfg(not(RUST_BITMAP_HARDENED))]
> +        if !($cond) {
> +            pr_err!($($arg)*);
> +            return
> +        }
> +    }
> +}
> +
> +/// Represents an owned bitmap.
> +///
> +/// Wraps underlying C bitmap API. See [`CBitmap`] for available
> +/// methods.
> +///
> +/// # Examples
> +///
> +/// Basic usage
> +///
> +/// ```
> +/// use kernel::alloc::flags::GFP_KERNEL;
> +/// use kernel::bitmap::Bitmap;
> +///
> +/// let mut b = Bitmap::new(16, GFP_KERNEL)?;
> +///
> +/// assert_eq!(16, b.len());
> +/// for i in 0..16 {
> +///     if i % 4 == 0 {
> +///       b.set_bit(i);
> +///     }
> +/// }
> +/// assert_eq!(Some(0), b.next_bit(0));
> +/// assert_eq!(Some(1), b.next_zero_bit(0));
> +/// assert_eq!(Some(4), b.next_bit(1));
> +/// assert_eq!(Some(5), b.next_zero_bit(4));
> +/// assert_eq!(Some(12), b.last_bit());
> +/// # Ok::<(), Error>(())
> +/// ```
> +///
> +/// # Invariants
> +///
> +/// * `inner.nbits` is `<= i32::MAX` and never changes.
> +/// * if `inner.nbits <= bindings::BITS_PER_LONG`, then `inner.repr` is
> +///   a `usize`.
> +/// * otherwise, `inner.repr` holds a non-null pointer to an initialized
> +///   array of `unsigned long` that is large enough to hold `nbits` bits.

There is no `inner` in the struct.

> +pub struct Bitmap {
> +    /// Representation of bitmap.
> +    repr: BitmapRepr,
> +    /// Length of this bitmap. Must be `<= i32::MAX`.
> +    nbits: usize,
> +}
> +
> +impl core::ops::Deref for Bitmap {
> +    type Target = CBitmap;
> +
> +    fn deref(&self) -> &CBitmap {
> +        let ptr = if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            // SAFETY: Bitmap is represented inline.
> +            unsafe { core::ptr::addr_of!(self.repr.bitmap) }

This can use the raw ref syntax, `&raw const self.repr.bitmap`.

> +        } else {
> +            // SAFETY: Bitmap is represented as array of `unsigned long`.
> +            unsafe { self.repr.ptr.as_ptr() }
> +        };
> +
> +        // SAFETY: We got the right pointer and invariants of [`Bitmap`] hold.
> +        // An inline bitmap is treated like an array with single element.
> +        unsafe { CBitmap::from_raw(ptr, self.nbits) }
> +    }
> +}
> +
> +impl core::ops::DerefMut for Bitmap {
> +    fn deref_mut(&mut self) -> &mut CBitmap {
> +        let ptr = if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            // SAFETY: Bitmap is represented inline.
> +            unsafe { core::ptr::addr_of_mut!(self.repr.bitmap) }

Same here, `&raw mut self.repr.bitmap`.

[...]

> +    /// Set bit with index `index`, atomically.
> +    ///
> +    /// This is a relaxed atomic operation (no implied memory barriers).
> +    ///
> +    /// ATTENTION: The naming convention differs from C, where the corresponding
> +    /// function is called `set_bit`.
> +    ///
> +    /// If RUST_BITMAP_HARDENED is not enabled and `index` is greater than
> +    /// or equal to `self.len()`, does nothing.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if RUST_BITMAP_HARDENED is enabled and `index` is greater than
> +    /// or equal to `self.len()`.
> +    #[inline]
> +    pub fn set_bit_atomic(&self, index: usize) {
> +        bitmap_assert_return!(
> +            index < self.len(),
> +            "Bit `index` must be < {}, was {}",
> +            self.len(),
> +            index
> +        );
> +        // SAFETY: `index` is within bounds and the caller has ensured that
> +        // there is no mix of non-atomic and atomic operations.
> +        unsafe { bindings::set_bit(index as u32, self.as_ptr() as *mut usize) };

Maybe use `.cast_mut()` instead of `as *mut usize`?

[...]

> +    /// Clear `index` bit, atomically.
> +    ///
> +    /// This is a relaxed atomic operation (no implied memory barriers).
> +    ///
> +    /// ATTENTION: The naming convention differs from C, where the corresponding
> +    /// function is called `clear_bit`.
> +    ///
> +    /// If RUST_BITMAP_HARDENED is not enabled and `index` is greater than
> +    /// or equal to `self.len()`, does nothing.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if RUST_BITMAP_HARDENED is enabled and `index` is greater than
> +    /// or equal to `self.len()`.
> +    #[inline]
> +    pub fn clear_bit_atomic(&self, index: usize) {
> +        bitmap_assert_return!(
> +            index < self.len(),
> +            "Bit `index` must be < {}, was {}",
> +            self.len(),
> +            index
> +        );
> +        // SAFETY: `index` is within bounds and the caller has ensured that
> +        // there is no mix of non-atomic and atomic operations.
> +        unsafe { bindings::clear_bit(index as u32, self.as_ptr() as *mut usize) };

Same here. `cast_mut` won't silently change the type unlike `as` casts so
it's a bit safer.

> +    }
> +
> +    /// Copy `src` into this [`Bitmap`] and set any remaining bits to zero.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let mut long_bitmap = Bitmap::new(256, GFP_KERNEL)?;
> +    //
> +    /// assert_eq!(None, long_bitmap.last_bit());
> +    //
> +    /// let mut short_bitmap = Bitmap::new(16, GFP_KERNEL)?;
> +    //
> +    /// short_bitmap.set_bit(7);
> +    /// long_bitmap.copy_and_extend(&short_bitmap);
> +    /// assert_eq!(Some(7), long_bitmap.last_bit());
> +    ///
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn copy_and_extend(&mut self, src: &Bitmap) {
> +        let len = core::cmp::min(src.nbits, self.len());
> +        // SAFETY: access to `self` and `src` is within bounds.
> +        unsafe {
> +            bindings::bitmap_copy_and_extend(
> +                self.as_mut_ptr(),
> +                src.as_ptr(),
> +                len as u32,
> +                self.len() as u32,
> +            )

Would this cause a data race if `src` is concurrently (atomically)
modified? The C function seems to use a plain `memcpy` which is not atomic.

> +        };
> +    }
> +
> +    /// Finds last set bit.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> +    /// use kernel::bitmap::Bitmap;
> +    ///
> +    /// let bitmap = Bitmap::new(64, GFP_KERNEL)?;
> +    ///
> +    /// match bitmap.last_bit() {
> +    ///     Some(idx) => {
> +    ///         pr_info!("The last bit has index {idx}.\n");
> +    ///     }
> +    ///     None => {
> +    ///         pr_info!("All bits in this bitmap are 0.\n");
> +    ///     }
> +    /// }
> +    /// # Ok::<(), AllocError>(())
> +    /// ```
> +    #[inline]
> +    pub fn last_bit(&self) -> Option<usize> {
> +        // SAFETY: `_find_next_bit` access is within bounds due to invariant.
> +        let index = unsafe { bindings::_find_last_bit(self.as_ptr(), self.len()) };

The C function uses non-atomic reads, so this might cause data races too.

> +        if index >= self.len() {
> +            None
> +        } else {
> +            Some(index)
> +        }
> +    }

Pekka

Powered by blists - more mailing lists