Message-Id: <D91AOKOTDXWC.7R5K5DI87QU4@nvidia.com>
Date: Tue, 08 Apr 2025 22:34:32 +0900
From: "Alexandre Courbot" <acourbot@...dia.com>
To: "Danilo Krummrich" <dakr@...nel.org>
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 Mon Apr 7, 2025 at 8:01 PM JST, Danilo Krummrich wrote:
> 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."

Yeah ExactSizeIterator is not the solution to this, since it can be
implemented without an unsafe block and the implementer is perfectly
free to provide an incorrect value - so we cannot trust its result.

>
> Acknowledging the latter, I think we should implement our own trait for this
> instead. Our own version of TrustedLen seems reasonable to me.

That sounds reasonable and would greatly simplify the code (and remove
most of my fears about its optimization). Let me explore that direction.

Thanks,
Alex.

Powered by blists - more mailing lists