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

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

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.
 
> 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". 

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

> Also, we should add #[track_caller] to these methods so that the line
> number in the panic message is taken from the caller rather than this
> file.
> 
> > > +        }
> > > +    }
> > > +
> > > +    /// 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