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: <D9DM3AR3FUAF.6JSNSB9WAJ4T@nvidia.com>
Date: Wed, 23 Apr 2025 10:02:58 +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 Wed Apr 23, 2025 at 2:03 AM JST, Danilo Krummrich wrote:
>> Well, that turned out to be an interesting rabbit hole.
>> 
>> Leveraging the existing traits seems a bit difficult:
>> 
>> - `ExactSizeIterator` cannot be implemented for adapters that increase the
>>   length of their iterators, because if one of them is already `usize::MAX` long
>>   then the size wouldn't be exact anymore. [1]
>> 
>> - And `TrustedLen` cannot be implemented for adapters that make an iterator
>>   shorter, because if the iterator returns more than `usize::MAX` items (i.e.
>>   has an upper bound set to `None`) then the adapter can't predict the actual
>>   length. [2]
>
> Why is this a problem for the above implementation of Vec::extend()?
>
> I just looked it up and it seems that std [1] does the same thing. Do I miss
> anything?
>
> [1] https://github.com/rust-lang/rust/blob/master/library/alloc/src/vec/spec_extend.rs#L25

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.