`BTreeSet` causes general protection fault with zero-sized key-value pairs and jemalloc

[apasel422]

foo.rs:

use std::collections::BTreeSet;

fn main() {
    let _: BTreeSet<()> = BTreeSet::new();
}

Output:

> rustc --version
rustc 1.5.0-nightly (cff041170 2015-09-17)
> rustc foo.rs
> valgrind ./foo
==15717== Memcheck, a memory error detector
==15717== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==15717== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==15717== Command: ./foo
==15717== 
==15717== Invalid read of size 1
==15717==    at 0x11D791: je_mallocx (in /home/andrew/foo)
==15717==    by 0x10D1DF: heap::allocate::hef78f640aa355f8bPda (in /home/andrew/foo)
==15717==    by 0x10CA6E: btree::node::Node$LT$K$C$$u20$V$GT$::new_leaf::h84712443304502014 (in /home/andrew/foo)
==15717==    by 0x10CA06: btree::node::Node$LT$K$C$$u20$V$GT$::make_leaf_root::h5239528127300894605 (in /home/andrew/foo)
==15717==    by 0x10C9B4: btree::map::BTreeMap$LT$K$C$$u20$V$GT$::with_b::h8455151666287840927 (in /home/andrew/foo)
==15717==    by 0x10C953: btree::map::BTreeMap$LT$K$C$$u20$V$GT$::new::h4727297226639213121 (in /home/andrew/foo)
==15717==    by 0x10C92C: btree::set::BTreeSet$LT$T$GT$::new::h6672219473307838625 (in /home/andrew/foo)
==15717==    by 0x10C90D: main::h42b03f129f44e909faa (in /home/andrew/foo)
==15717==    by 0x114D64: sys_common::unwind::try::try_fn::h14601444602367533931 (in /home/andrew/foo)
==15717==    by 0x111D78: __rust_try (in /home/andrew/foo)
==15717==    by 0x1149D8: rt::lang_start::h7135051af8990a95Zkx (in /home/andrew/foo)
==15717==    by 0x10E799: main (in /home/andrew/foo)
==15717==  Address 0x200000000013feff is not stack'd, malloc'd or (recently) free'd
==15717== 
==15717== 
==15717== Process terminating with default action of signal 11 (SIGSEGV)
==15717==  General Protection Fault
==15717==    at 0x11D791: je_mallocx (in /home/andrew/foo)
==15717==    by 0x10D1DF: heap::allocate::hef78f640aa355f8bPda (in /home/andrew/foo)
==15717==    by 0x10CA6E: btree::node::Node$LT$K$C$$u20$V$GT$::new_leaf::h84712443304502014 (in /home/andrew/foo)
==15717==    by 0x10CA06: btree::node::Node$LT$K$C$$u20$V$GT$::make_leaf_root::h5239528127300894605 (in /home/andrew/foo)
==15717==    by 0x10C9B4: btree::map::BTreeMap$LT$K$C$$u20$V$GT$::with_b::h8455151666287840927 (in /home/andrew/foo)
==15717==    by 0x10C953: btree::map::BTreeMap$LT$K$C$$u20$V$GT$::new::h4727297226639213121 (in /home/andrew/foo)
==15717==    by 0x10C92C: btree::set::BTreeSet$LT$T$GT$::new::h6672219473307838625 (in /home/andrew/foo)
==15717==    by 0x10C90D: main::h42b03f129f44e909faa (in /home/andrew/foo)
==15717==    by 0x114D64: sys_common::unwind::try::try_fn::h14601444602367533931 (in /home/andrew/foo)
==15717==    by 0x111D78: __rust_try (in /home/andrew/foo)
==15717==    by 0x1149D8: rt::lang_start::h7135051af8990a95Zkx (in /home/andrew/foo)
==15717==    by 0x10E799: main (in /home/andrew/foo)
==15717== 
==15717== HEAP SUMMARY:
==15717==     in use at exit: 32 bytes in 1 blocks
==15717==   total heap usage: 5 allocs, 4 frees, 976 bytes allocated
==15717== 
==15717== LEAK SUMMARY:
==15717==    definitely lost: 0 bytes in 0 blocks
==15717==    indirectly lost: 0 bytes in 0 blocks
==15717==      possibly lost: 0 bytes in 0 blocks
==15717==    still reachable: 32 bytes in 1 blocks
==15717==         suppressed: 0 bytes in 0 blocks
==15717== Rerun with --leak-check=full to see details of leaked memory
==15717== 
==15717== For counts of detected and suppressed errors, rerun with: -v
==15717== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)

Segmentation fault (core dumped)

[apasel422]

The BTreeMap expansion of this is:

use std::collections::BTreeMap;

fn main() {
    let _: BTreeMap<(), ()> = BTreeMap::new();
}

Note that BTreeMap<(), i32> does not cause this problem.

[apasel422]

Note also that this is only the case with jemalloc. The following runs successfully:

#![feature(alloc_system)]
extern crate alloc_system;

use std::collections::BTreeMap;

fn main() {
    let _: BTreeMap<(), ()> = BTreeMap::new();
}

[apasel422]

Actually, this is just related to calling jemalloc with 0 for the size:

#![feature(alloc, heap_api)]

extern crate alloc;

fn main() {
    let size = std::mem::size_of::<()>();
    let align = std::mem::align_of::<()>();

    unsafe {
        alloc::heap::allocate(size, align);
    }
}

> valgrind ./foo
==16282== Memcheck, a memory error detector
==16282== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==16282== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==16282== Command: ./foo
==16282== 
==16282== Invalid read of size 1
==16282==    at 0x11B7B1: je_mallocx (in /home/andrew/foo)
==16282==    by 0x10C78F: heap::allocate::hef78f640aa355f8bPda (in /home/andrew/foo)
==16282==    by 0x10C710: main::h2fbc6b3b4aacc11afaa (in /home/andrew/foo)
==16282==    by 0x112D94: sys_common::unwind::try::try_fn::h14601444602367533931 (in /home/andrew/foo)
==16282==    by 0x10FDA8: __rust_try (in /home/andrew/foo)
==16282==    by 0x112A08: rt::lang_start::h7135051af8990a95Zkx (in /home/andrew/foo)
==16282==    by 0x10C7C9: main (in /home/andrew/foo)
==16282==  Address 0x200000000013dd7f is not stack'd, malloc'd or (recently) free'd
==16282== 
==16282== 
==16282== Process terminating with default action of signal 11 (SIGSEGV)
==16282==  General Protection Fault
==16282==    at 0x11B7B1: je_mallocx (in /home/andrew/foo)
==16282==    by 0x10C78F: heap::allocate::hef78f640aa355f8bPda (in /home/andrew/foo)
==16282==    by 0x10C710: main::h2fbc6b3b4aacc11afaa (in /home/andrew/foo)
==16282==    by 0x112D94: sys_common::unwind::try::try_fn::h14601444602367533931 (in /home/andrew/foo)
==16282==    by 0x10FDA8: __rust_try (in /home/andrew/foo)
==16282==    by 0x112A08: rt::lang_start::h7135051af8990a95Zkx (in /home/andrew/foo)
==16282==    by 0x10C7C9: main (in /home/andrew/foo)
==16282== 
==16282== HEAP SUMMARY:
==16282==     in use at exit: 32 bytes in 1 blocks
==16282==   total heap usage: 5 allocs, 4 frees, 976 bytes allocated
==16282== 
==16282== LEAK SUMMARY:
==16282==    definitely lost: 0 bytes in 0 blocks
==16282==    indirectly lost: 0 bytes in 0 blocks
==16282==      possibly lost: 0 bytes in 0 blocks
==16282==    still reachable: 32 bytes in 1 blocks
==16282==         suppressed: 0 bytes in 0 blocks
==16282== Rerun with --leak-check=full to see details of leaked memory
==16282== 
==16282== For counts of detected and suppressed errors, rerun with: -v
==16282== ERROR SUMMARY: 2 errors from 1 contexts (suppressed: 0 from 0)
Segmentation fault (core dumped)

[apasel422]

We should probably apply a temporary fix for this (and audit all other uses of alloc::heap::allocate), though @gereeter's BTreeMap rewrite will remove the direct allocation calls.

[alexcrichton]

triage: I-nominated

Seems pretty serious and something we may want to fix soon!

[alexcrichton]

cc @gankro

[apasel422]

I have a potential PR in progress, just running tests locally.