Re: [PATCH v9 3/5] rust: add bitmap API.

[Boqun Feng <boqun.feng@gmail.com>]

On Mon, May 26, 2025 at 03:01:32PM +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@google.com>
> Suggested-by: Yury Norov <yury.norov@gmail.com>
> Signed-off-by: Burak Emir <bqe@google.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@google.com>
> +M:	Burak Emir <bqe@google.com>
> +R:	Yury Norov <yury.norov@gmail.com>
> +S:	Maintained
> +F:	rust/kernel/bitmap.rs
> +
>  BITOPS API
>  M:	Yury Norov <yury.norov@gmail.com>
>  R:	Rasmus Villemoes <linux@rasmusvillemoes.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],

This is the same as #[repr(align(8)] on 64bit architecture? If so, maybe
we should do:

	#[cfg_attr(CONFIG_64BIT, repr(align(8)))]
	#[cfg_attr(not(CONFIG_64BIT), repr(align(4)))]
	pub struct CBitmap {
	    data: [()],
	}

? I find it slightly better because it's explicit on the targeted
alignment.

> +    data: [()],
> +}
> +
> +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);

Need "// INVARIANT:" here and in from_raw_mut() to explain why the
references are valid.

> +        unsafe { &*(data as *const CBitmap) }
> +    }
> +
> +    /// Borrows a C bitmap exclusively.
> +    ///
> +    /// # 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`]
> +    /// * no concurrent access may happen.
> +    pub unsafe fn from_raw_mut<'a>(ptr: *mut usize, nbits: usize) -> &'a mut CBitmap {
> +        let data: *mut [()] = core::ptr::slice_from_raw_parts_mut(ptr.cast(), nbits);
> +        unsafe { &mut *(data as *mut CBitmap) }
> +    }
> +
> +    /// 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`].
> +    pub fn len(&self) -> usize {
> +        self.data.len()
> +    }
> +}
> +
[...]
> +/// Enable ownership transfer to other threads.
> +///
> +/// # Safety
> +///
> +/// We own the underlying bitmap representation.

Usually the comment here should be a:

// SAFETY: <explain why Bitmap is Send>

"# Safety" is for describing the safety requirement.

> +unsafe impl Send for Bitmap {}
> +
> +/// Enable unsynchronized concurrent access to [`Bitmap`] through shared references.
> +///
> +/// # Safety
> +///
> +/// * When no thread performs any mutations, concurrent access is safe.
> +/// * Mutations are permitted through atomic operations and interior mutability.
> +///   All such methods are marked unsafe, to account for the lack of ordering
> +///   guarantees. Callers must acknowledge that updates may be observed in any
> +///   order.

I think this comment is out-of-date. What makes `Bitmap` is that all
methods will immutable references are either atomic or read-only (more
accurately, `Bitmap`'s deref() will return a reference to a `CBitmap`
which is `Sync`).

> +unsafe impl Sync for Bitmap {}
> +
> +impl Drop for Bitmap {
> +    fn drop(&mut self) {
> +        if self.nbits <= bindings::BITS_PER_LONG as _ {
> +            return;
> +        }
> +        // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
> +        //
> +        // INVARIANT: there is no other use of the `self.ptr` after this
> +        // call and the value is being dropped so the broken invariant is
> +        // not observable on function exit.
> +        unsafe { bindings::bitmap_free(self.repr.ptr.as_ptr()) };
> +    }
> +}
> +
> +impl Bitmap {
> +    /// Constructs a new [`Bitmap`].
> +    ///
> +    /// Fails with [`AllocError`] when the [`Bitmap`] could not be allocated. This
> +    /// includes the case when `nbits` is greater than `i32::MAX`.
> +    #[inline]
> +    pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
> +        if nbits <= bindings::BITS_PER_LONG as _ {
> +            return Ok(Bitmap {
> +                repr: BitmapRepr { bitmap: 0 },
> +                nbits,
> +            });
> +        }
> +        if nbits > i32::MAX.try_into().unwrap() {
> +            return Err(AllocError);
> +        }
> +        let nbits_u32 = u32::try_from(nbits).unwrap();
> +        // SAFETY: `bindings::BITS_PER_LONG < nbits` and `nbits <= i32::MAX`.
> +        let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> +        let ptr = NonNull::new(ptr).ok_or(AllocError)?;
> +        // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.
> +        return Ok(Bitmap {
> +            repr: BitmapRepr { ptr },
> +            nbits,
> +        });
> +    }
> +
> +    /// Returns length of this [`CBitmap`].

Copy-pasta? It should be "[`Bitmap`]".

> +    #[inline]
> +    pub fn len(&self) -> usize {
> +        self.nbits
> +    }
> +}
> +

Probably need:

unsafe impl Sync for CBitmap { }

> +impl CBitmap {
> +    /// Set bit with index `index`.
> +    ///
> +    /// ATTENTION: `set_bit` is non-atomic, which differs from the naming
> +    /// convention in C code. The corresponding C function is `__set_bit`.
> +    ///
> +    /// If RUST_BITMAP_HARDENED is not enabled and `index` is greater than
> +    /// or equal to `self.nbits`, does nothing.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if RUST_BITMAP_HARDENED is enabled and `index` is greater than
> +    /// or equal to `self.nbits`.
> +    #[inline]
> +    pub fn set_bit(&mut self, index: usize) {
> +        bitmap_assert_return!(
> +            index < self.len(),
> +            "Bit `index` must be < {}, was {}",
> +            self.len(),
> +            index
> +        );
> +        // SAFETY: Bit `index` is within bounds.
> +        unsafe { bindings::__set_bit(index as u32, self.as_mut_ptr()) };
> +    }
> +
[...]

Regards,
Boqun