On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.no...@gmail.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
