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

[Yury Norov <yury.norov@gmail.com>]

On Mon, May 19, 2025 at 10:41:58PM +0200, Burak Emir wrote:
> On Mon, May 19, 2025 at 8:22 PM Yury Norov <yury.norov@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.

I'd implement the Send method, or just say that the method is to be
implemented in future when it will be needed.
 
> > >     * 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).

OK. Can you also mention it? And if we'll need to share bitmaps
between C and Rust modules, are you going to create a new class, or
extent the existing one?

> > > 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?

No. set_bit(), clear_bit() and test_bit() don't know the bitmap size
and can't check out-of-boundary. 

But your Rust set_bit() does! You can check boundaries unconditionally,
and throw errors depending on the hardening config. If user wants to set
an out-of-boundary bit, you should just do nothing,

> > 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.
 
The hardening should be disabled for benchmarking reasons, isn't?