[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Message-ID: <Z_OwmEKHgsZlt2cs@pollux>
Date: Mon, 7 Apr 2025 13:01:44 +0200
From: Danilo Krummrich <dakr@...nel.org>
To: Alexandre Courbot <acourbot@...dia.com>
Cc: Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>,
Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>,
Björn Roy Baron <bjorn3_gh@...tonmail.com>,
Benno Lossin <benno.lossin@...ton.me>,
Andreas Hindborg <a.hindborg@...nel.org>,
Alice Ryhl <aliceryhl@...gle.com>, Trevor Gross <tmgross@...ch.edu>,
Joel Fernandes <joelagnelf@...dia.com>,
John Hubbard <jhubbard@...dia.com>, rust-for-linux@...r.kernel.org,
linux-kernel@...r.kernel.org
Subject: Re: [PATCH v3] rust: alloc: implement `extend` for `Vec`
On Sun, Apr 06, 2025 at 10:01:55PM +0900, Alexandre Courbot wrote:
> KVec currently has `extend_with` and `extend_from_slice` methods, but no
> way extend a vector from a regular iterator as provided by the `Extend`
> trait.
>
> Due to the need to provide the GFP flags, `Extend` cannot be implemented
> directly, so simply define a homonymous method that takes an extra
> `flags` argument.
This is the same approach I took with Vec::collect(); I think this is fine for
now. One we attempt to implement more collections, we should implement our own
Extend and FromIterator traits.
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index ae9d072741cedbb34bed0be0c20cc75472aa53be..b3c4227e232cca3b5c17930abc63810240b9c4da 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -454,30 +454,86 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
> }
> }
>
> +impl<T, A: Allocator> Vec<T, A> {
Please re-use the existing impl block above, i.e.
diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index b3c4227e232c..72659b017553 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -452,9 +452,7 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
Ok(())
}
-}
-impl<T, A: Allocator> Vec<T, A> {
/// Extends the vector by the elements of `iter`.
///
/// This uses [`Iterator::size_hint`] to optimize memory reallocations, but will work even with
> + /// Extends the vector by the elements of `iter`.
> + ///
> + /// This uses [`Iterator::size_hint`] to optimize memory reallocations, but will work even with
> + /// imprecise implementations - albeit in a non-optimal way.
> + ///
> + /// This method returns an error if a memory reallocation required to accommodate the new items
> + /// failed. In this case, callers must assume that some (but not all) elements of `iter` might
> + /// have been added to the vector.
> + ///
> + /// # Note on optimal behavior and correctness
> + ///
> + /// The efficiency of this method depends on how reliable the [`Iterator::size_hint`]
> + /// implementation of the `iter` is.
> + ///
> + /// It performs optimally with at most a single memory reallocation if the lower bound of
> + /// `size_hint` is the exact number of items actually yielded.
> + ///
> + /// If `size_hint` is more vague, there may be as many memory reallocations as necessary to
> + /// cover the whole iterator from the successive lower bounds returned by `size_hint`.
> + ///
> + /// If `size_hint` signals more items than actually yielded by the iterator, some unused memory
> + /// might be reserved.
> + ///
> + /// Finally, whenever `size_hint` returns `(0, Some(0))`, the method assumes that no more items
> + /// are yielded by the iterator and returns. This may result in some items not being added if
> + /// there were still some remaining.
> + ///
> + /// In the kernel most iterators are expected to have a precise and correct `size_hint`
> + /// implementation, so this should nicely optimize out for these cases.
I agree, hence I think we should enforce to be provided with a guaranteed
correct size hint and simplify the code. I think we should extend the signature.
pub fn extend<I>(&mut self, iter: I, flags: Flags) -> Result<(), AllocError>
where
I: IntoIterator<Item = T>,
I::IntoIter: ExactSizeIterator,
And implement ExactSizeIterator for IntoIter.
The only thing that bothers me a bit is that the documentation [1] of
ExactSizeIterator sounds a bit ambiguous.
It says: "When implementing an ExactSizeIterator, you must also implement
Iterator. When doing so, the implementation of Iterator::size_hint *must*
return the exact size of the iterator."
But it also says: "Note that this trait is a safe trait and as such does not and
cannot guarantee that the returned length is correct. This means that unsafe
code must not rely on the correctness of Iterator::size_hint. The unstable and
unsafe TrustedLen trait gives this additional guarantee."
Acknowledging the latter, I think we should implement our own trait for this
instead. Our own version of TrustedLen seems reasonable to me.
[1] https://doc.rust-lang.org/std/iter/trait.ExactSizeIterator.html
Powered by blists - more mailing lists