Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

The implementation of InPlaceIterable for Peekable is unsound #85322

Closed
SkiFire13 opened this issue May 15, 2021 · 6 comments · Fixed by #85340
Closed

The implementation of InPlaceIterable for Peekable is unsound #85322

SkiFire13 opened this issue May 15, 2021 · 6 comments · Fixed by #85340
Labels
C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-libs Relevant to the library team, which will review and decide on the PR/issue.

Comments

@SkiFire13
Copy link
Contributor

SkiFire13 commented May 15, 2021

This code leads to an out of bounds write, makes the assert fail and triggers miri:

fn main() {
    let v = vec![0; 5];
    let mut i = v.into_iter().peekable();
    i.peek();
    let v = i.clone().collect::<Vec<_>>();
    assert!(v.len() <= v.capacity());
}

playground

The problem is that after cloning a Peekable the inner iterator can no longer be considered advanced, but the Peekable may still yield the peeked element without advancing it, thus breaking the contract of InPlaceIterable.

@SkiFire13 SkiFire13 added the C-bug Category: This is a bug. label May 15, 2021
@jonas-schievink jonas-schievink added I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness T-libs Relevant to the library team, which will review and decide on the PR/issue. labels May 15, 2021
@rustbot rustbot added the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label May 15, 2021
@the8472
Copy link
Member

the8472 commented May 15, 2021

This can be fixed by either removing InPlaceIterable from Peekable or by changing the Clone impl of IntoIter to clone the exact state of IntoIter rather than allocating a smaller one. The latter may be unnecessarily costly when cloning a mostly-exhausted iterator, but on the other hand it would preserve the optimization.
So I'd try the first one first and do a perf run to see what the impact is (when it was introduced it mostly helped rustdoc) and try the latter if there's a significant regression.

@the8472
Copy link
Member

the8472 commented May 15, 2021

It may also be possible to fix this by specializing Clone on Peekable to look into its SourceIter (if available) and do a custom clone of its source.
I'll see if specialization is powerful enough to pull that off.

@the8472
Copy link
Member

the8472 commented May 15, 2021

Hrm, I think it would be possible to do that but it would require some additional helper traits or methods tailored to just this use-case since core doesn't know about alloc. That's probably too much hackery for this optimization.

@aDotInTheVoid
Copy link
Member

aDotInTheVoid commented May 15, 2021

This also effects stable

https://godbolt.org/z/4P5sbP6xf

@rustbot modify labels: regression-from-stable-to-stable

@rustbot rustbot added the regression-from-stable-to-stable Performance or correctness regression from one stable version to another. label May 15, 2021
@hameerabbasi
Copy link
Contributor

Is it a regression though?

Marking as P-critical according to the discussion in WG-prio.

@rustbot modify labels -I-prioritize +P-critical

@rustbot rustbot added P-critical Critical priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels May 18, 2021
@SkiFire13
Copy link
Contributor Author

SkiFire13 commented May 18, 2021

Is it a regression though?

Technically when #70793 was merged it broke any crate that used code like this (which is not that unexpected like exploting panics and stuff like that). In fact I found this bug due to a project written in only safe rust code that was segfaulting

@bors bors closed this as completed in df70463 May 20, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
C-bug Category: This is a bug. I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness P-critical Critical priority regression-from-stable-to-stable Performance or correctness regression from one stable version to another. T-libs Relevant to the library team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

6 participants