Segfault on iter().collect() (2.0.0-alpha-5)

[josephg]

I'm running into a segfault when calling some_iter.collect() into a SmallVec. The problem happens when the smallvec spills and needs to allocate, eventually leading to a segfault in the realloc call.

I'll try and make a minimal reproducing test.

The problem shows up in both debug and release mode, running on the latest stable rust compiler (1.78.0).

Smallvec 1.x works fine.

Valgrind has the gory details. The first problem it spots is an invalid memmove:

==21584== Thread 2 list::op_iter:::
==21584== Invalid write of size 8
==21584==    at 0x485293B: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584==    by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mod.rs:1493)
==21584==    by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mut_ptr.rs:1491)
==21584==    by 0x3F41C2: smallvec::SmallVec<T,_>::push_heap (lib.rs:968)
==21584==    by 0x3EA6EF: smallvec::SmallVec<T,_>::extend_impl (lib.rs:1519)
==21584==    by 0x3E481F: <smallvec::SmallVec<T,_> as core::iter::traits::collect::FromIterator<T>>::from_iter (lib.rs:1838)
==21584==    by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)

Full valgrind trace below.

``` $ valgrind target/debug/deps/diamond_types-f42d3b862ee83a0c --ignored fix_cs --nocapture ==21584== Memcheck, a memory error detector ==21584== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==21584== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info ==21584== Command: target/debug/deps/diamond_types-f42d3b862ee83a0c --ignored fix_cs --nocapture ==21584==

running 1 test
==21584== Thread 2 list::op_iter:::
==21584== Invalid write of size 8
==21584== at 0x485293B: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mod.rs:1493)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mut_ptr.rs:1491)
==21584== by 0x3F41C2: smallvec::SmallVec<T,>::push_heap (lib.rs:968)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== by 0x20DB18: diamond_types::list::op_iter::test::fix_cs::{{closure}} (op_iter.rs:399)
==21584== by 0x21AEE7: core::ops::function::FnOnce::call_once (function.rs:250)
==21584== by 0x4C30FE: test::__rust_begin_short_backtrace (function.rs:250)
==21584== by 0x4C2782: test::run_test::{{closure}} (lib.rs:644)
==21584== by 0x48A162: std::sys_common::backtrace::__rust_begin_short_backtrace (lib.rs:595)
==21584== Address 0x4ea2360 is 0 bytes after a block of size 256 free'd
==21584== at 0x484DCD3: realloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2365B1: alloc::alloc::realloc (alloc.rs:138)
==21584== by 0x3F7B6C: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:238)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3F4162: smallvec::SmallVec<T,>::push_heap (lib.rs:966)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== Block was alloc'd at
==21584== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2361F1: alloc::alloc::alloc (alloc.rs:100)
==21584== by 0x3F7956: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:220)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3ED4F8: smallvec::SmallVec<T,>::push (lib.rs:949)
==21584== by 0x3EA664: smallvec::SmallVec<T,>::extend_impl (lib.rs:1508)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584==
==21584== Invalid write of size 8
==21584== at 0x4852943: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mod.rs:1493)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mut_ptr.rs:1491)
==21584== by 0x3F41C2: smallvec::SmallVec<T,>::push_heap (lib.rs:968)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== by 0x20DB18: diamond_types::list::op_iter::test::fix_cs::{{closure}} (op_iter.rs:399)
==21584== by 0x21AEE7: core::ops::function::FnOnce::call_once (function.rs:250)
==21584== by 0x4C30FE: test::__rust_begin_short_backtrace (function.rs:250)
==21584== by 0x4C2782: test::run_test::{{closure}} (lib.rs:644)
==21584== by 0x48A162: std::sys_common::backtrace::__rust_begin_short_backtrace (lib.rs:595)
==21584== Address 0x4ea2368 is 8 bytes after a block of size 256 free'd
==21584== at 0x484DCD3: realloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2365B1: alloc::alloc::realloc (alloc.rs:138)
==21584== by 0x3F7B6C: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:238)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3F4162: smallvec::SmallVec<T,>::push_heap (lib.rs:966)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== Block was alloc'd at
==21584== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2361F1: alloc::alloc::alloc (alloc.rs:100)
==21584== by 0x3F7956: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:220)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3ED4F8: smallvec::SmallVec<T,>::push (lib.rs:949)
==21584== by 0x3EA664: smallvec::SmallVec<T,>::extend_impl (lib.rs:1508)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584==
==21584== Invalid write of size 8
==21584== at 0x485294B: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mod.rs:1493)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mut_ptr.rs:1491)
==21584== by 0x3F41C2: smallvec::SmallVec<T,>::push_heap (lib.rs:968)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== by 0x20DB18: diamond_types::list::op_iter::test::fix_cs::{{closure}} (op_iter.rs:399)
==21584== by 0x21AEE7: core::ops::function::FnOnce::call_once (function.rs:250)
==21584== by 0x4C30FE: test::__rust_begin_short_backtrace (function.rs:250)
==21584== by 0x4C2782: test::run_test::{{closure}} (lib.rs:644)
==21584== by 0x48A162: std::sys_common::backtrace::__rust_begin_short_backtrace (lib.rs:595)
==21584== Address 0x4ea2370 is 16 bytes after a block of size 256 free'd
==21584== at 0x484DCD3: realloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2365B1: alloc::alloc::realloc (alloc.rs:138)
==21584== by 0x3F7B6C: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:238)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3F4162: smallvec::SmallVec<T,>::push_heap (lib.rs:966)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== Block was alloc'd at
==21584== at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x2361F1: alloc::alloc::alloc (alloc.rs:100)
==21584== by 0x3F7956: smallvec::RawSmallVec<T,>::try_grow_raw (lib.rs:220)
==21584== by 0x3F35D3: smallvec::SmallVec<T,>::try_grow (lib.rs:1022)
==21584== by 0x3ED1B4: smallvec::SmallVec<T,>::grow (lib.rs:1008)
==21584== by 0x3EF6AA: smallvec::SmallVec<T,>::reserve (lib.rs:1062)
==21584== by 0x3ED4F8: smallvec::SmallVec<T,>::push (lib.rs:949)
==21584== by 0x3EA664: smallvec::SmallVec<T,>::extend_impl (lib.rs:1508)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584==
==21584== Invalid write of size 8
==21584== at 0x4852953: memmove (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mod.rs:1493)
==21584== by 0x3F41C2: write<diamond_types::list::operation::TextOperation> (mut_ptr.rs:1491)
==21584== by 0x3F41C2: smallvec::SmallVec<T,>::push_heap (lib.rs:968)
==21584== by 0x3EA6EF: smallvec::SmallVec<T,>::extend_impl (lib.rs:1519)
==21584== by 0x3E481F: <smallvec::SmallVec<T,> as core::iter::traits::collect::FromIterator>::from_iter (lib.rs:1838)
==21584== by 0x291CA3: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==21584== by 0x395258: diamond_types::list::op_iter::::as_chunked_operation_vec (op_iter.rs:290)
==21584== by 0x3AF4E1: diamond_types::list::op_iter::test::fix_cs (op_iter.rs:407)
==21584== by 0x20DB18: diamond_types::list::op_iter::test::fix_cs::{{closure}} (op_iter.rs:399)
==21584== by 0x21AEE7: core::ops::function::FnOnce::call_once (function.rs:250)
==21584== by 0x4C30FE: test::__rust_begin_short_backtrace (function.rs:250)
==21584== by 0x4C2782: test::run_test::{{closure}} (lib.rs:644)
==21584== by 0x48A162: std::sys_common::backtrace::__rust_begin_short_backtrace (lib.rs:595)
==21584== Address 0x4ea2378 is 24 bytes after a block of size 256 in arena "client"
==21584==

valgrind: m_mallocfree.c:303 (get_bszB_as_is): Assertion 'bszB_lo == bszB_hi' failed.
valgrind: Heap block lo/hi size mismatch: lo = 7894, hi = 0.
This is probably caused by your program erroneously writing past the
end of a heap block and corrupting heap metadata. If you fix any
invalid writes reported by Memcheck, this assertion failure will
probably go away. Please try that before reporting this as a bug.

</details>

[josephg]

This is all you need to reproduce the problem:

use smallvec::SmallVec;

/// This is just a stupid wrapper around an iterator that overrides size_hint.
struct IterNoHint<I: Iterator>(I);
impl<I: Iterator> Iterator for IterNoHint<I> {
    type Item = I::Item;
    fn next(&mut self) -> Option<Self::Item> { self.0.next() }
    
    // no implementation of size_hint means it returns (0, None).
}

#[derive(Debug, Clone, Eq, PartialEq)]
enum SomeEnum { A, B }

fn main() {
    let x = vec![SomeEnum::A, SomeEnum::B, SomeEnum::A];

    let _y: SmallVec<SomeEnum, 1> = IterNoHint(x.into_iter()).collect();
}

The code runs to completion, but memory corruption is occurring. (Unfortunately, in this case the memory corruption doesn't cause a crash). But you can see the issue easily enough in valgrind:

$ cargo build && valgrind target/debug/smallvec-repro 
==72004== Memcheck, a memory error detector
==72004== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==72004== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==72004== Command: target/debug/smallvec-repro
==72004== 
==72004== Invalid write of size 1
==72004==    at 0x12022A: write<smallvec_repro::SomeEnum> (mod.rs:1493)
==72004==    by 0x12022A: write<smallvec_repro::SomeEnum> (mut_ptr.rs:1491)
==72004==    by 0x12022A: smallvec::SmallVec<T,_>::push_heap (lib.rs:968)
==72004==    by 0x11F90C: smallvec::SmallVec<T,_>::extend_impl (lib.rs:1519)
==72004==    by 0x11F2BB: <smallvec::SmallVec<T,_> as core::iter::traits::collect::FromIterator<T>>::from_iter (lib.rs:1838)
==72004==    by 0x121393: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==72004==    by 0x12104D: smallvec_repro::main (main.rs:25)
==72004==    by 0x12283D: core::ops::function::FnOnce::call_once (function.rs:250)
==72004==    by 0x1212D0: std::sys_common::backtrace::__rust_begin_short_backtrace (backtrace.rs:155)
==72004==    by 0x122273: std::rt::lang_start::{{closure}} (rt.rs:166)
==72004==    by 0x13A262: std::rt::lang_start_internal (function.rs:284)
==72004==    by 0x122247: std::rt::lang_start (rt.rs:165)
==72004==    by 0x1210A0: main (in /home/seph/src/smallvec-repro/target/debug/smallvec-repro)
==72004==  Address 0x4ac2ba2 is 0 bytes after a block of size 2 free'd
==72004==    at 0x484DCD3: realloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==72004==    by 0x121E21: alloc::alloc::realloc (alloc.rs:138)
==72004==    by 0x12072A: smallvec::RawSmallVec<T,_>::try_grow_raw (lib.rs:238)
==72004==    by 0x11FFB3: smallvec::SmallVec<T,_>::try_grow (lib.rs:1022)
==72004==    by 0x11FB84: smallvec::SmallVec<T,_>::grow (lib.rs:1008)
==72004==    by 0x11FDBA: smallvec::SmallVec<T,_>::reserve (lib.rs:1062)
==72004==    by 0x1201EB: smallvec::SmallVec<T,_>::push_heap (lib.rs:966)
==72004==    by 0x11F90C: smallvec::SmallVec<T,_>::extend_impl (lib.rs:1519)
==72004==    by 0x11F2BB: <smallvec::SmallVec<T,_> as core::iter::traits::collect::FromIterator<T>>::from_iter (lib.rs:1838)
==72004==    by 0x121393: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==72004==    by 0x12104D: smallvec_repro::main (main.rs:25)
==72004==    by 0x12283D: core::ops::function::FnOnce::call_once (function.rs:250)
==72004==  Block was alloc'd at
==72004==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==72004==    by 0x121A61: alloc::alloc::alloc (alloc.rs:100)
==72004==    by 0x120516: smallvec::RawSmallVec<T,_>::try_grow_raw (lib.rs:220)
==72004==    by 0x11FFB3: smallvec::SmallVec<T,_>::try_grow (lib.rs:1022)
==72004==    by 0x11FB84: smallvec::SmallVec<T,_>::grow (lib.rs:1008)
==72004==    by 0x11FDBA: smallvec::SmallVec<T,_>::reserve (lib.rs:1062)
==72004==    by 0x11FC2E: smallvec::SmallVec<T,_>::push (lib.rs:949)
==72004==    by 0x11F8BB: smallvec::SmallVec<T,_>::extend_impl (lib.rs:1508)
==72004==    by 0x11F2BB: <smallvec::SmallVec<T,_> as core::iter::traits::collect::FromIterator<T>>::from_iter (lib.rs:1838)
==72004==    by 0x121393: core::iter::traits::iterator::Iterator::collect (iterator.rs:2003)
==72004==    by 0x12104D: smallvec_repro::main (main.rs:25)
==72004==    by 0x12283D: core::ops::function::FnOnce::call_once (function.rs:250)
==72004== 
==72004== 
==72004== HEAP SUMMARY:
==72004==     in use at exit: 0 bytes in 0 blocks
==72004==   total heap usage: 13 allocs, 13 frees, 2,166 bytes allocated
==72004== 
==72004== All heap blocks were freed -- no leaks are possible
==72004== 
==72004== For lists of detected and suppressed errors, rerun with: -s
==72004== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

[mbrubeck]

Fixed by #354.

[gendx]

FYI, given the memory corruption, I've opened an issue to file a security advisory for this: rustsec/advisory-db#1961.

I don't expect many crates to depend on the alpha versions, but given that the smallvec crate is (transitively) depended on by more than 30k crates I think it's worth reporting in suitable tooling.