LLVM miscompiles large stack allocations

[Cl00e9ment]

I tried this code:

use std::thread;

const KILO: usize = 1024;
const MEGA: usize = 1024 * KILO;
const GIGA: usize = 1024 * MEGA;

const BUFFER_SIZE: usize = 4 * GIGA;
const REQUIRED_STACK_SIZE: usize = 512 * MEGA + BUFFER_SIZE;

fn main() {
    thread::Builder::new()
        .stack_size(REQUIRED_STACK_SIZE)
        .spawn(perform_double_free).unwrap()
        .join().unwrap();
}

fn perform_double_free() {
    make_noise();
    let mut buffer = [0; BUFFER_SIZE];
    write_to_buffer(&mut buffer, 0);
}

fn make_noise() {
    vec![0].append(&mut vec![0]);
}

fn write_to_buffer(buffer: &mut [u8; BUFFER_SIZE], mut i: usize) {
    i += 4096;
    if i >= BUFFER_SIZE {
        return;
    }
    write_to_buffer(buffer, i);
    buffer[i] = 1;
}

I expected the program to exit normally.
Instead, this happened:

free(): double free detected in tcache 2
Aborted

Meta

Tested on Linux with the following Rust versions :

• rustc 1.63.0 (4b91a6ea7 2022-08-08)
• rustc 1.64.0-beta.3 (82bf34178 2022-08-18)
• rustc 1.65.0-nightly (015a824f2 2022-08-22)

Only reproducible with --release.
Can be reproduced on Windows inside a Rust Docker container.

⚠️ WARNING ⚠️
The program may use about 5 GiB of memory and may hang the system. So be sure to have enough space and be ready to kill the process.

Backtrace
No backtrace is printed with RUST_BACKTRACE=1.

[5225225]

Can reproduce that it emits free(): double free detected in tcache 2.

So this does indeed seem to be either a false positive on that side, or unsoundness.

I have no idea why it only appears if you have a 4GB long stack buffer.... (Maybe using an int somewhere to store offsets?)

Interesting data point: it does not warn if you use address sanitizer.

[Noratrieb]

On x86_64-unknown-linux-musl, I get fish: 'cargo run --release --target x8…' terminated by signal SIGSEGV (Address boundary error). On GNU, I get the double free report as well.

[5225225]

Also, valgrind does complain

==3885223== Memcheck, a memory error detector
==3885223== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
==3885223== Using Valgrind-3.19.0 and LibVEX; rerun with -h for copyright info
==3885223== Command: /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh
==3885223== 
==3885223== Warning: set address range perms: large range [0x59c8e000, 0x179c8f000) (noaccess)
==3885223== Warning: client switching stacks?  SP change: 0x79c8ddc0 --> 0x179c8ddd8
==3885223==          to suppress, use: --max-stackframe=4294967320 or greater
==3885223== Warning: client switching stacks?  SP change: 0x179c8dde8 --> 0x79c8ddd0
==3885223==          to suppress, use: --max-stackframe=4294967320 or greater
==3885223== Thread 2:
==3885223== Invalid read of size 4
==3885223==    at 0x110A91: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==  Address 0x4a92090 is 0 bytes inside a block of size 4 free'd
==3885223==    at 0x4846CC3: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3885223==    by 0x10F191: alloc::raw_vec::finish_grow (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==    by 0x10F281: alloc::raw_vec::RawVec<T,A>::reserve::do_reserve_and_handle (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==    by 0x110A87: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==  Block was alloc'd at
==3885223==    at 0x4841888: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3885223==    by 0x110A53: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223== 
==3885223== Invalid free() / delete / delete[] / realloc()
==3885223==    at 0x484426F: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3885223==    by 0x110AA9: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==  Address 0x4a92090 is 0 bytes inside a block of size 4 free'd
==3885223==    at 0x4846CC3: realloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3885223==    by 0x10F191: alloc::raw_vec::finish_grow (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==    by 0x10F281: alloc::raw_vec::RawVec<T,A>::reserve::do_reserve_and_handle (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==    by 0x110A87: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223==  Block was alloc'd at
==3885223==    at 0x4841888: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==3885223==    by 0x110A53: scratchIyxkUIBfh::perform_double_free (in /home/jess/.cache/cargo/target/release/scratchIyxkUIBfh)
==3885223== 
==3885223== Warning: client switching stacks?  SP change: 0x79c8ddd0 --> 0x179c8dde8
==3885223==          to suppress, use: --max-stackframe=4294967320 or greater
==3885223==          further instances of this message will not be shown.
==3885223== Warning: set address range perms: large range [0x59c8e000, 0x179c8f000) (noaccess)
==3885223== 
==3885223== HEAP SUMMARY:
==3885223==     in use at exit: 4 bytes in 1 blocks
==3885223==   total heap usage: 22 allocs, 22 frees, 2,853 bytes allocated
==3885223== 
==3885223== LEAK SUMMARY:
==3885223==    definitely lost: 4 bytes in 1 blocks
==3885223==    indirectly lost: 0 bytes in 0 blocks
==3885223==      possibly lost: 0 bytes in 0 blocks
==3885223==    still reachable: 0 bytes in 0 blocks
==3885223==         suppressed: 0 bytes in 0 blocks
==3885223== Rerun with --leak-check=full to see details of leaked memory
==3885223== 
==3885223== For lists of detected and suppressed errors, rerun with: -s
==3885223== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)

what this means, I have no clue.

[Xiretza]

Here's a slightly minimized reproducer:

use std::thread;

const KILO: usize = 1024;
const MEGA: usize = 1024 * KILO;
const GIGA: usize = 1024 * MEGA;

// max failing
//const BUFFER_SIZE: usize = 4 * GIGA + 16;
const BUFFER_SIZE: usize = 4 * GIGA;
const REQUIRED_STACK_SIZE: usize = 512 * MEGA + BUFFER_SIZE;

fn main() {
    thread::Builder::new()
        .stack_size(REQUIRED_STACK_SIZE)
        .spawn(perform_double_free)
        .unwrap()
        .join()
        .unwrap();
}

fn perform_double_free() {
    let v1 = vec![0];
    let v2 = vec![0];

    verbose_drop(v2);
    verbose_drop(v1);

    println!("never reached");

    let buffer = [0u8; BUFFER_SIZE];
    mark_buffer_used(&buffer);
}

#[inline(never)]
fn verbose_drop(x: Vec<i32>) {
    println!("dropping vec at {:?}", x.as_ptr());
}

fn mark_buffer_used(buffer: &[u8]) {
    println!("{}", buffer[0]);
}

Prints:

dropping vec at 0x7f4aec000cc0
dropping vec at 0x7f4aec000cc0
free(): double free detected in tcache 2

If BUFFER_SIZE is changed to 4 * GIGA + 1, it instead prints the following and segfaults:

dropping vec at 0x7f8b40000cc0
dropping vec at 0x1

Relevant section from the assembly (with 4 * GIGA + 1):

    8b74:       bf 04 00 00 00          mov    $0x4,%edi
    8b79:       be 04 00 00 00          mov    $0x4,%esi
    8b7e:       ff 15 dc 8e 04 00       call   *0x48edc(%rip)        # 51a60 <_GLOBAL_OFFSET_TABLE_+0x208>  (NB: __rust_alloc)
    8b84:       48 85 c0                test   %rax,%rax
    8b87:       0f 84 33 01 00 00       je     8cc0 <play::perform_double_free+0x160>
    8b8d:       c7 00 00 00 00 00       movl   $0x0,(%rax)
    8b93:       48 89 44 24 10          mov    %rax,0x10(%rsp)
    8b98:       48 c7 44 24 18 01 00    movq   $0x1,0x18(%rsp)
    8b9f:       00 00
    8ba1:       48 c7 44 24 20 01 00    movq   $0x1,0x20(%rsp)
    8ba8:       00 00
    8baa:       bf 04 00 00 00          mov    $0x4,%edi
    8baf:       be 04 00 00 00          mov    $0x4,%esi
    8bb4:       ff 15 a6 8e 04 00       call   *0x48ea6(%rip)        # 51a60 <_GLOBAL_OFFSET_TABLE_+0x208>  (NB: __rust_alloc)
    8bba:       48 85 c0                test   %rax,%rax
    8bbd:       0f 84 0f 01 00 00       je     8cd2 <play::perform_double_free+0x172>
    8bc3:       c7 00 00 00 00 00       movl   $0x0,(%rax)
    8bc9:       48 89 04 24             mov    %rax,(%rsp)
    8bcd:       48 c7 44 24 08 01 00    movq   $0x1,0x8(%rsp)
    8bd4:       00 00
    8bd6:       48 c7 44 24 10 01 00    movq   $0x1,0x10(%rsp)
    8bdd:       00 00
    8bdf:       40 b5 01                mov    $0x1,%bpl
    8be2:       48 89 e7                mov    %rsp,%rdi
    8be5:       e8 26 01 00 00          call   8d10 <play::verbose_drop>
    8bea:       48 8b 44 24 20          mov    0x20(%rsp),%rax
    8bef:       48 89 44 24 10          mov    %rax,0x10(%rsp)
    8bf4:       0f 10 44 24 10          movups 0x10(%rsp),%xmm0
    8bf9:       0f 29 04 24             movaps %xmm0,(%rsp)
    8bfd:       31 ed                   xor    %ebp,%ebp
    8bff:       48 89 e7                mov    %rsp,%rdi
    8c02:       e8 09 01 00 00          call   8d10 <play::verbose_drop>

The first vector is stored at 0x10(%rsp) -- 0x20(%rsp) (at 0x8b93), and is then partially overwritten by the second vector, stored at (%rsp) -- 0x10(%rsp) (at 0x8bc9).

[Cl00e9ment]

This issue seems related to this one.

[Xiretza]

I've been able to bisect this back to 2018-05-03 as the earliest failing nightly (2018-04-30 does not reproduce it).

[Xiretza]

@Cl00e9ment, could you post the following?

@rustbot label +T-compiler +I-unsound

I think those labels should be right, there is definitely a miscompilation happening somewhere. Hopefully that'll draw some attention here.

Edit: nevermind, worked when I did it! Apparently the author-only restriction is only on pull requests.

[j-tai]

Possibly the same issue as #83060

[pnkfelix]

@wesleywiser points out that this might be related to LLVM issue llvm/llvm-project#48911

[pnkfelix]

Discussed during T-compiler 2023 Q1 P-high review

See commented added to end of #83060, starting with #83060 (comment)

[KonaeAkira]

Program output seems to have changed since rustc 1.70.0 (90c541806 2023-05-31). Now outputs:

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow
Aborted (core dumped)

[wesleywiser]

This should be fixed by llvm/llvm-project#101840

[jieyouxu]

P-high triage: upstream PR was reverted due to hitting an assertion, cause/solution unclear, reverted in llvm/llvm-project@768598b.