linux-kernel - Re: [PATCH v3 17/25] rust: alloc: implement `collect` for `IntoIter`

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAH5fLgiPyEs+zMCmTSQjhBuG8T4SU1j8LWKGBucz_--X-MxY=A@mail.gmail.com>
Date: Fri, 2 Aug 2024 14:08:34 +0200
From: Alice Ryhl <aliceryhl@...gle.com>
To: Danilo Krummrich <dakr@...nel.org>
Cc: ojeda@...nel.org, alex.gaynor@...il.com, wedsonaf@...il.com, 
	boqun.feng@...il.com, gary@...yguo.net, bjorn3_gh@...tonmail.com, 
	benno.lossin@...ton.me, a.hindborg@...sung.com, akpm@...ux-foundation.org, 
	daniel.almeida@...labora.com, faith.ekstrand@...labora.com, 
	boris.brezillon@...labora.com, lina@...hilina.net, mcanal@...lia.com, 
	zhiw@...dia.com, acurrid@...dia.com, cjia@...dia.com, jhubbard@...dia.com, 
	airlied@...hat.com, ajanulgu@...hat.com, lyude@...hat.com, 
	linux-kernel@...r.kernel.org, rust-for-linux@...r.kernel.org, 
	linux-mm@...ck.org
Subject: Re: [PATCH v3 17/25] rust: alloc: implement `collect` for `IntoIter`

On Fri, Aug 2, 2024 at 2:02 PM Danilo Krummrich <dakr@...nel.org> wrote:
>
> On Fri, Aug 02, 2024 at 09:08:48AM +0200, Alice Ryhl wrote:
> > On Thu, Aug 1, 2024 at 5:37 PM Danilo Krummrich <dakr@...nel.org> wrote:
> > >
> > > On Thu, Aug 01, 2024 at 05:10:22PM +0200, Alice Ryhl wrote:
> > > > On Thu, Aug 1, 2024 at 2:08 AM Danilo Krummrich <dakr@...nel.org> wrote:
> > > > >
> > > > > Currently, we can't implement `FromIterator`. There are a couple of
> > > > > issues with this trait in the kernel, namely:
> > > > >
> > > > >   - Rust's specialization feature is unstable. This prevents us to
> > > > >     optimze for the special case where `I::IntoIter` equals `Vec`'s
> > > > >     `IntoIter` type.
> > > > >   - We also can't use `I::IntoIter`'s type ID either to work around this,
> > > > >     since `FromIterator` doesn't require this type to be `'static`.
> > > > >   - `FromIterator::from_iter` does return `Self` instead of
> > > > >     `Result<Self, AllocError>`, hence we can't properly handle allocation
> > > > >     failures.
> > > > >   - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle
> > > > >     additional allocation flags.
> > > > >
> > > > > Instead, provide `IntoIter::collect`, such that we can at least convert
> > > > > `IntoIter` into a `Vec` again.
> > > > >
> > > > > Signed-off-by: Danilo Krummrich <dakr@...nel.org>
> > > >
> > > > I'm not convinced a collect implementation specific to IntoIter is necessary?
> > >
> > > For the reasons above, we can't implement `FromIterator`. At some point we may
> > > want to implement our own kernel `FromIterator` trait, but that's out of scope
> > > for this series.
> > >
> > > For now, I just want to provide a way to get a `Vec` from `IntoIter` again,
> > > which without `Vec::collect` would be impossible.
> >
> > If you have a need for a collect on this particular kind of iterator, then okay.
>
> Even once we have our own `FromIterator` trait, we probably want to keep this
> specific one besides the generic `collect` for optimization. With the generic
> one we'd otherwise copy into a new `Vec`.
>
> >
> > > > > +
> > > > > +        // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed to be
> > > > > +        // smaller than `cap`. Depending on `alloc` this operation may shrink the buffer or leaves
> > > > > +        // it as it is.
> > > > > +        ptr = match unsafe { A::realloc(Some(buf.cast()), layout, flags) } {
> > > >
> > > > Why would you shrink it? You can just keep the capacity.
> > >
> > > What if the vector was pretty huge and meanwhile as advanced by a lot? I think
> > > we don't want to waste those resources.
> > >
> > > Ideally the corresponding `Allocator` implements a proper heuristic for when to
> > > actually shrink. For instance, krealloc() never shrinks, and it's probably not
> > > worth it. For vrealloc() though we clearly want to shrink properly (i.e. unmap
> > > and free spare pages) at some point.
> >
> > The Rust Vec never shrinks unless explicitly requested. But I guess
> > it's okay either way.
>
> It actually does, see [1]. But Rust's `Vec` does it less efficiently. It either
> keeps the `Vec` as it is, or creates a whole new one.
>
> [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/vec/spec_from_iter.rs#L39

Huh, surprising.

Reviewed-by: Alice Ryhl <aliceryhl@...gle.com>

Alice