Message-ID: <CACQBu=XQ9QrHwzfXZiJf6-uSLTucpr2k=BwRhrDCkVA3wX7-ug@mail.gmail.com>
Date: Mon, 19 May 2025 22:41:58 +0200
From: Burak Emir <bqe@...gle.com>
To: Yury Norov <yury.norov@...il.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 v8 3/5] rust: add bitmap API.

On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.norov@...il.com> wrote:
>
> On Mon, May 19, 2025 at 04:17:03PM +0000, Burak Emir wrote:
> > Provides an abstraction for C bitmap API and bitops operations.
> > 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:
> >
> >     * Ownership transfer of a Bitmap is restricted so that it cannot
> >     be passed between threads (does not implement `Send`).
>
> Can you explain why you decided to not implement it? You can 'share' a
> reference, but prohibit 'sending' it...
>

My intention here was to be conservative. It seems safe to send a
Bitmap to a different thread,
in the sense that it would not cause data races.

Maybe it would be better to commit now to keep Bitmap "send"able - for all time.
It would however constrain the API quite a bit. One could never use this API
with a thread-local bitmap.

> >     * all (non-atomic) mutating operations require a &mut reference which
> >     amounts to exclusive access.
> >
> >     * It is permissible to pass shared references &Bitmap between
> >     threads, and we expose atomic operations through interior mutability.
> >     Since these atomic operations do not provide any ordering guarantees,
> >     we mark these as `unsafe`. Anyone who calls the atomic methods needs
> >     to document that the lack of ordering is safe.
> >
> >   * The Rust API offers `{set,clear}_bit` vs `{set,clear}_bit_atomic`,
> >     which is different from the C naming convention (set_bit vs __set_bit).
> >
> >   * we include enough operations for the API to be useful, but not all
> >     operations are exposed yet in order to avoid dead code. This commit
>
> This sentence and the following one say the same thing. Can you please
> rephrase?

Thanks for catching that, will do.

> >     includes enough to enable a Rust implementation of an Android Binder
> >     data structure that was introduced in commit 15d9da3f818c ("binder:
> >     use bitmap for faster descriptor lookup"), which can be found in
> >     drivers/android/dbitmap.h. We need this in order to upstream the Rust
> >     port of Android Binder driver.
> >
> >   * We follow the C API closely and fine-grained approach to safety:
> >
> >     * Low-level bit-ops methods get a safe API with bounds checks.
> >
> >     * methods correspond to find_* C methods tolerate out-of-bounds
> >     arguments. Since these are already safe we the same behavior, and
> >     return results using `Option` types to represent "not found".
>
> Nit: the above 2 lines look misaligned. Everywhere else you align
> items such that new lines under asterisk align with the first
> character, not the asterisk itself.

Yes, will fix.

> >
> >   * the Rust API is optimized to represent the bitmap inline if it would
> >     take the space of a pointer. This saves allocations which is
>
> s/take the space of/fits into/
>
> >     relevant in the Binder use case.
> >
> >   * Bounds checks where out-of-bounds values would not result in
> >     immediate access faults are configured via a RUST_BITMAP_HARDENED
> >     config.
> >
> > The underlying C bitmap is *not* exposed, and must never be exposed
> > (except in tests). Exposing the representation would lose all static
> > guarantees, and moreover would prevent the optimized representation of
> > short bitmaps.
>
> Does it mean that all existing kernel bitmaps declared in C are not
> accessible in Rust as well?

At the moment, we do not permit construction of a Rust Bitmap from an
existing C bitmap.
The point is more about the other direction though, not being able to
pass the Rust-owned bitmap to C code.

One could think of an API that requires an exclusively owned (no one
else has access) pointer to a C bitmap to Rust.
Though there is no general way to ensure that property, there are
situations where it would make sense (e.g. newly created).

> > 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.
>
> This should go in cover letter as well. Did you run any performance
> tests against the native bitmaps?

ok, I will mention it there. I have not run this against the Rust native bitmap.
I'd need to find out how to get a Rust native bitmap into kernel Rust code.

[...]

> > +    /// 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`.
> > +    ///
> > +    /// # Panics
> > +    ///
> > +    /// Panics if `index` is greater than or equal to `self.nbits`.
> > +    #[inline]
> > +    pub fn set_bit(&mut self, index: usize) {
> > +        assert!(
> > +            index < self.nbits,
> > +            "Bit `index` must be < {}, was {}",
> > +            self.nbits,
> > +            index
> > +        );
>
> Shouldn't this assertion be protected with hardening too? I already
> said that: panicking on  out-of-boundary access with hardening
> disabled is a wrong way to go.

I considered it, but could not convince myself that __set_bit etc are
actually always safe.
For the methods that have the hardening assert, I was sure, but for
this one, not.

Are all bit ops guaranteed to handle out-of-bounds gracefully?

> Can you turn your bitmap_hardening_assert() to just bitmap_assert(),
> which panics only if hardening is enabled, and otherwise just prints
> error with pr_err()?

If there is no risk of undefined behavior, then I agree that checking
bounds is hardening.
If a missing bounds check loses safety, we then we should not skip it.

> Did you measure performance impact of hardening? Are those numbers in
> cover letter collected with hardening enabled or disabled? If
> performance impact is measurable, it should be mentioned in config
> description.

The hardening was enabled and it crossed my mind to mention it.
Given that not all methods have hardening, I though it might be misleading.

I'll have a more complete comparision and description in the next version.

[...]

> > +    /// Clear `index` bit, atomically.
> > +    ///
> > +    /// ATTENTION: The naming convention differs from C, where the corresponding
> > +    /// function is called `clear_bit`.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// This is a relaxed atomic operation (no implied memory barriers, no
> > +    /// ordering guarantees). The caller must ensure that this is safe, as
>
> Memory barriers is an implementation of 'ordering guarantees', so all
> this sounds tautology.
>

ok, i will remove one of them.

[...]
> > diff --git a/security/Kconfig.hardening b/security/Kconfig.hardening
> > index 3fe9d7b945c4..926665bbc8f2 100644
> > --- a/security/Kconfig.hardening
> > +++ b/security/Kconfig.hardening
> > @@ -324,6 +324,15 @@ config LIST_HARDENED
> >
> >         If unsure, say N.
> >
> > +config RUST_BITMAP_HARDENED
> > +     bool "Check integrity of linked list manipulation"
>
> Wah?

oh, thanks for catching that.

Thanks,
Burak

Powered by blists - more mailing lists