VecDeque: length 0 underflow and bogus values from pop_front(), triggered by a certain sequence of reserve(), push_back(), make_contiguous(), pop_front()
ayourtch opened this issue · 9 comments
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
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
}
Hmm, if it double-frees then why does Miri not catch it?
Assigning P-critical
and removing I-prioritize
as discussed in the prioritization working group.
Some time ago I've read somewhere that Rust stdlib VecDeque is cursed. I didn't believe them. I'm changing opinion... -.-
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...
Still, this is memory-unsafe, right?
Yes, It's still a use-after-free regardless
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
).