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

VecDeque: length 0 underflow and bogus values from pop_front(), triggered by a certain sequence of reserve(), push_back(), make_contiguous(), pop_front() #79808

Closed
ayourtch opened this issue Dec 7, 2020 · 9 comments · Fixed by #79814
Assignees
Labels
A-collections Area: `std::collection` 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 T-libs Relevant to the library team, which will review and decide on the PR/issue. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@ayourtch
Copy link

ayourtch commented Dec 7, 2020

This is my first bug report, so please correct me s if I miss anything :-)

I use VecDeque in a toy application (https://github.com/ayourtch/flex-sftp-server) which is handling external reads in a loop, and does possible partial handling of the input.

My pattern is I call reserve(N) before push_back() N times, then make_contiguous(), then doing some pop_front(). I noticed the app was behaving badly, and was able to generate a stand-alone test case which shows the bug.

The code is pretty boring and repetitive, so I put it at https://github.com/ayourtch/deq-bug/ to avoid spamming here.

Just issue "cargo run" after cloning out that code, and look for the word "BUG" within the terminal output:

According to the docs, pop_front() on an empty VecDeque should return None.

Instead, this happens:

pop: Some(75)
pop: Some(6e)
pop: Some(74)
pop: Some(75)
deq len: 0
pop: Some(2f)
BUG ^^^
deq len: 31
pop: Some(75)
pop: Some(62)
pop: Some(75)
pop: Some(6e)

If I set the boolean "do_reserve" to be false, thus getting rid of all the reserve() calls, I get the expected behavior:

pop: Some(75)
pop: Some(6e)
pop: Some(74)
pop: Some(75)
deq len: 0
pop: None
BUG ^^^
deq len: 0
pop: None
pop: None
pop: None
pop: None
pop: None

The same happens if I set "do_make_contiguous" to false as well - so calling both functions is a prerequisite to trigger the bug.
The same thing happens in debug and release builds.

Meta

The below is the version I found it in, but thanks a lot to Steve Klabnik for also testing it on nightly and getting the same buggy behavior.

rustc --version --verbose:

rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-unknown-linux-gnu
release: 1.48.0
LLVM version: 11.0

@ayourtch ayourtch added the C-bug Category: This is a bug. label Dec 7, 2020
@jonas-schievink jonas-schievink added A-collections Area: `std::collection` E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example T-libs Relevant to the library team, which will review and decide on the PR/issue. labels Dec 7, 2020
@naim94a
Copy link

naim94a commented Dec 7, 2020

I created a minimal sample:

use std::collections::VecDeque;

fn ab(dq: &mut VecDeque<i32>, sz: usize) {
    for i in 0..sz {
        dq.push_back(i as _);
    }
    dq.make_contiguous();
    for _ in 0..sz {
        dq.pop_front();
    }
}

fn main() {
    let mut dq = VecDeque::with_capacity(2);
    ab(&mut dq, 2);
    ab(&mut dq, 3);
    
    dbg!(dq.len()); // this is zero
    
    dbg!(dq.pop_front()); // uaf+double frees
}

@jonas-schievink jonas-schievink added I-unsound Issue: A soundness hole (worst kind of bug), see: https://en.wikipedia.org/wiki/Soundness and removed E-needs-mcve Call for participation: This issue has a repro, but needs a Minimal Complete and Verifiable Example labels Dec 7, 2020
@rustbot rustbot added the I-prioritize Issue: Indicates that prioritization has been requested for this issue. label Dec 7, 2020
@camelid
Copy link
Member

camelid commented Dec 7, 2020

Hmm, if it double-frees then why does Miri not catch it?

@camelid camelid added P-critical Critical priority and removed I-prioritize Issue: Indicates that prioritization has been requested for this issue. labels Dec 7, 2020
@camelid
Copy link
Member

camelid commented Dec 7, 2020

Assigning P-critical and removing I-prioritize as discussed in the prioritization working group.

@camelid camelid added the T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. label Dec 7, 2020
@leonardo-m
Copy link

Some time ago I've read somewhere that Rust stdlib VecDeque is cursed. I didn't believe them. I'm changing opinion... -.-

@naim94a
Copy link

naim94a commented Dec 7, 2020

Hmm, if it double-frees then why does Miri not catch it?

This specific case doesn't double free (i32::drop is a noop), using a Box might have been a better example...

@camelid
Copy link
Member

camelid commented Dec 7, 2020

Still, this is memory-unsafe, right?

@naim94a
Copy link

naim94a commented Dec 7, 2020

Yes, It's still a use-after-free regardless

@lcnr

This comment has been minimized.

@lcnr lcnr self-assigned this Dec 7, 2020
@camelid
Copy link
Member

camelid commented Dec 7, 2020

Yes, It's still a use-after-free regardless

@naim94a Based on my conversation with lcnr, jonas-schievink, and others on Zulip, it seems that using make_contiguous with copy types is not UB (it still exhibits a bug though!) because copy types aren't freed. It is UB with non-copy types though (e.g. Box).

@bors bors closed this as completed in d32c320 Dec 10, 2020
JohnTitor added a commit to JohnTitor/rust that referenced this issue Jan 11, 2021
JohnTitor added a commit to JohnTitor/rust that referenced this issue Jan 12, 2021
bors added a commit to rust-lang-ci/rust that referenced this issue Jan 12, 2021
Rollup of 8 pull requests

Successful merges:

 - rust-lang#79757 (Replace tabs earlier in diagnostics)
 - rust-lang#80600 (Add `MaybeUninit` method `array_assume_init`)
 - rust-lang#80880 (Move some tests to more reasonable directories)
 - rust-lang#80897 (driver: Use `atty` instead of rolling our own)
 - rust-lang#80898 (Add another test case for rust-lang#79808)
 - rust-lang#80917 (core/slice: remove doc comment about scoped borrow)
 - rust-lang#80927 (Replace a simple `if let` with the `matches` macro)
 - rust-lang#80930 (fix typo in trait method mutability mismatch help)

Failed merges:

r? `@ghost`
`@rustbot` modify labels: rollup
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-collections Area: `std::collection` 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 T-libs Relevant to the library team, which will review and decide on the PR/issue. T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Development

Successfully merging a pull request may close this issue.

7 participants