Skip to content

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

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.

Sign up for GitHub

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

Jump to bottom
Closed
apasel422 opened this issue Sep 18, 2015 · 7 comments · Fixed by #28497
Closed

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

apasel422 opened this issue Sep 18, 2015 · 7 comments · Fixed by #28497
Labels
A-collections Area: `std::collections` T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.

Comments

@apasel422
Copy link
Contributor

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
Copy link
Contributor Author

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
Copy link
Contributor Author

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 apasel422 changed the title BTreeSet causes general protection fault with zero-sized key-value pairs BTreeSet causes general protection fault with zero-sized key-value pairs and jemalloc Sep 18, 2015
@apasel422
Copy link
Contributor Author

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
Copy link
Contributor Author

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
Copy link
Member

triage: I-nominated

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

@alexcrichton alexcrichton added A-collections Area: `std::collections` T-libs-api Relevant to the library API team, which will review and decide on the PR/issue. and removed I-nominated labels Sep 18, 2015
@alexcrichton
Copy link
Member

cc @gankro

@apasel422
Copy link
Contributor Author

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

This was referenced Sep 18, 2015
Merged
Closed
bors added a commit that referenced this issue Sep 19, 2015
@bors
Auto merge of #28497 - apasel422:issue-28493, r=Gankro
6db1a0e 
When both the key and value types were zero-sized, `BTreeMap` previously
called `heap::allocate` with `size == 0` for leaf nodes, which is
undefined behavior, and jemalloc would attempt to read invalid memory,
crashing the process.

This avoids undefined behavior by allocating enough space to store one
edge in leaf nodes that would otherwise have `size == 0`. Although this
uses extra memory, maps with zero-sized key types that have sensible
implementations of the ordering traits can only contain a single
key-value pair (and therefore only a single leaf node), and maps with
key and value types that are both zero-sized have few uses, if any.

Furthermore, this is a temporary fix that will likely be unnecessary
once the `BTreeMap` implementation is rewritten to use parent pointers.

Closes #28493.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
A-collections Area: `std::collections` T-libs-api Relevant to the library API team, which will review and decide on the PR/issue.
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Avoid zero-sized leaf allocations in BTreeMap
3 participants
@alexcrichton @rust-highfive @apasel422