linux-kernel - Re: [PATCH v3] rust: alloc: implement `extend` for `Vec`

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: <D9DX39CF2RB7.IM219BZLVMCY@nvidia.com>
Date: Wed, 23 Apr 2025 18:40:07 +0900
From: "Alexandre Courbot" <acourbot@...dia.com>
To: "Alice Ryhl" <aliceryhl@...gle.com>
Cc: "Danilo Krummrich" <dakr@...nel.org>, "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>, "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 Wed Apr 23, 2025 at 5:51 PM JST, Alice Ryhl wrote:
> On Wed, Apr 23, 2025 at 10:02:58AM +0900, Alexandre Courbot wrote:
>> The problem I see is that if you try and do something like:
>> 
>>   vec.extend((0..10).into_iter().skip(2));
>> 
>> with the standard library, then the use of `skip` will remove the
>> `TrustedLen` implementation from the resulting iterator and
>> `extend_desugared` will be called instead of `extend_trusted`, which
>> could add some unwanted (and unexpected) overhead.
>> 
>> If we want an implementation of `extend` as simple as "confidently
>> increase the length of the vector and copy the new items into it, once",
>> then we need a trait that can be implemented on both shrinking and
>> extending adapters. Anything else and we might trick the caller into a
>> code path less efficient than expected (i.e. my original version, which
>> generates more core even for the obvious cases that are `extend_with`
>> and `extend_from_slice`). Or if we rely on `TrustedLen` solely in the
>> kernel, then `extend` could not be called at all with this particular
>> iterator.
>> 
>> There is also the fact that `TrustedLen` is behind a nightly feature,
>> which I guess is another obstacle for using it.
>
> The stdlib alloc crate relies on specialization to speed up methods
> related to iterators. We can't use specialization, so losing these
> optimizations is simply a cost of not using the upstream alloc library
> that we have to accept.

Yeah I was surprised to see

  impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
  where
      I: Iterator<Item = T>

and

  impl<T, I, A: Allocator> SpecExtend<T, I> for Vec<T, A>
  where
      I: TrustedLen<Item = T>

in the standard library, which clearly looks like an overlap. Didn't
know it was relying on a non-standard feature.

That's going to limit what we can do in the kernel, but nonetheless if
we can support only the cases that can be optimized I think we would
have our bases covered.