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

[ayourtch]

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

[naim94a]

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
}

[camelid]

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

[camelid]

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

[leonardo-m]

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

[naim94a]

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]

Still, this is memory-unsafe, right?

[naim94a]

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

[camelid]

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).