Re: [PATCH v3] rust: add bindings and API for bitmap.h and bitops.h.

[Alice Ryhl <aliceryhl@google.com>]

On Tue, Mar 11, 2025 at 10:33:10AM -0400, Yury Norov wrote:
> On Tue, Mar 11, 2025 at 10:07:15AM +0000, Alice Ryhl wrote:
> > On Mon, Mar 10, 2025 at 02:12:22PM -0400, Yury Norov wrote:
> > > On Mon, Mar 10, 2025 at 04:19:46PM +0000, Burak Emir wrote:
> > > > Adds a Rust bitmap API and necessary bitmap and bitops bindings.
> > > > These are for porting the approach from commit 15d9da3f818c ("binder:
> > > > use bitmap for faster descriptor lookup") to Rust. The functionality
> > > > in dbitmap.h makes use of bitmap and bitops.
> > > 
> > > Please add it in the same series that converts dbitmap to rust. This
> > > all is a dead code otherwise, right?
> > 
> > Rust Binder is not upstream yet. We are upstreaming its dependencies
> > before the driver itself, so there will be dead code no matter what. The
> > number of dependencies is so large that it's completely impractical to
> > land them together with the driver.
> 
> I don't ask to upstream all at once. But at least dbitmaps is less
> than 200 LOCs in C. Together with a test that demonstrates how you're
> using it, it would be enough.

Sounds good.

> > We can include a patch that includes the wrapper data structure that
> > Rust Binder builds on top of bitmap. We can also include a link to the
> > Rust Binder change that makes Binder start using this code.
> >
> > > > +            let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
> > > > +            // Zero-size allocation is ok and yields a dangling pointer.
> > > 
> > > Zero-sized allocation makes no sense, and usually is a sign of a bug.
> > > What for you explicitly allow it?
> > 
> > I do think that it makes sense to allow a bitmap of size zero. We allow
> > bitmaps of any other length. Why should that length be special?
> > 
> > Of course, I guess it might make sense to not call `bitmap_zalloc` when
> > calling `new(0)`? But kmalloc does seem to allow them.
> 
> Without looking at the code it's "I think vs you think". 

The include/linux/slab.h file says:

/*
 * ZERO_SIZE_PTR will be returned for zero sized kmalloc requests.
 *
 * Dereferencing ZERO_SIZE_PTR will lead to a distinct access fault.
 *
 * ZERO_SIZE_PTR can be passed to kfree though in the same way that NULL can.
 * Both make kfree a no-op.
 */
#define ZERO_SIZE_PTR ((void *)16)

> > > > +    /// Copies all bits from `src` and sets any remaining bits to zero.
> > > > +    ///
> > > > +    /// # Panics
> > > > +    ///
> > > > +    /// Panics if `src.nbits` has more bits than this bitmap.
> > > > +    #[inline]
> > > > +    pub fn copy_from_bitmap_and_extend(&mut self, src: &Bitmap) {
> > > > +        if self.nbits < src.nbits {
> > > > +            panic_not_in_bounds_le("src.nbits", self.nbits, src.nbits);
> > > 
> > > The _lt usually stands for 'less than', or '<'. And _le is 'less than or
> > > equal', or '<='. But in your code you do exactly opposite. Is that on
> > > purpose?
> > > 
> > > Also, you can make it similar to BUG_ON() semantics, so that it will
> > > be a single line of code, not 3:
> > > 
> > >         RUST_PANIC("Copy: out of bonds", self.nbits < src.nbits);
> > > 
> > > And to that extend, panic message should be available to all rust
> > > subsystems, just like BUG_ON().
> > 
> > We could use
> > assert!(src.nbits <= self.nbits, "Copy: out of bounds.");
> > 
> > but using these explicit function calls would generate less code and
> > avoid duplicating the error messages.
> 
> What I see is that you generate more code - 3 lines vs 1.
> 
> Do you have any numbers supporting your statement? Can you show how
> exactly the messages are duplicated when using assert()? Can this
> assert() be fixed to avoid duplication?

The statement comes from having multiple string literals containing
similar strings. They might get deduplicated if they're completely
equal, I guess. Having many methods call one shared function ensures
that the binary will only have one copy of the string literal.

> > > > +        }
> > > > +    }
> > > > +
> > > > +    /// Finds the next zero bit, searching up to `nbits` bits, with offset `offset`.
> > > > +    ///
> > > > +    /// # Panics
> > > > +    ///
> > > > +    /// Panics if `nbits` is too large for this bitmap.
> > > > +    #[inline]
> > > > +    pub fn find_next_zero_bit_upto_offset(&self, nbits: usize, offset: usize) -> usize {
> > > > +        if self.nbits < nbits {
> > > > +            panic_not_in_bounds_le("nbits", self.nbits, nbits);
> > > > +        }
> > > > +        // SAFETY: nbits == 0 and out-of-bounds offset is supported, and access is within bounds.
> > > 
> > > find_bit() functions are all safe against nbits == 0 or
> > > offset >= nbits. If you add those panics for hardening reasons - it's
> > > OK. If you add them to make your code safer - you don't need them. The
> > > C version is already safe.
> > 
> > Ah, that's nice! I do think it's still good to have them for hardening
> > reasons. Passing an out-of-bouds offset is a bug.
> 
> Ironically, you don't test the offset for safety.
> 
> Whether it's a bug or not - depends on algorithm you're implementing. 
> Check how for_each_set_bitrange() works. For it, offset >= nbits is
> expected, at last iteration. It's completely safe, although out-of-range.
> 
> Thanks,
> Yury