Space for large, constant arrays is allocated on the stack

[stevecheckoway]

When a large, constant array like

const ARRAY: [u32; LARGE_CONSTANT] = [ /* ... */ ];

is accessed directly (rather than through a reference) in a function like this

pub fn get(idx: usize) -> u32 {
    match idx {
        0..=8455 => ARRAY[idx],
        8550..=8645 => ARRAY[idx - 94],
        8740..=8835 => ARRAY[idx - 188],
        8930..=13127 => ARRAY[idx - 282],
        13206..=13299 => ARRAY[idx - 360],
        13396..=13489 => ARRAY[idx - 456],
        13586..=13679 => ARRAY[idx - 552],
        13966..=14059 => ARRAY[idx - 838],
        _ => 0,
    }
}

rustc appears to be allocating enough space to hold the whole array on the stack for each reference. With a large enough array times number of uses, this can cause the stack probe to fail. (I didn't check if the whole array is actually materialized on the stack each time or if only space for it is allocated.)

I expected rustc to not allocate space for the constant array and instead access it directly from the read-only memory segment of the executable.

Instead, when I run the code, I get

    Finished test [unoptimized + debuginfo] target(s) in 0.00s
     Running target/debug/deps/array_bug-d57a78204f1529fa

running 1 test

thread 'test::test' has overflowed its stack
fatal runtime error: stack overflow
error: test failed, to rerun pass '--lib'

Caused by:
  process didn't exit successfully: `/Users/steve/programming/array-bug/target/debug/deps/array_bug-d57a78204f1529fa` (signal: 6, SIGABRT: process abort signal)

Disassembling the binary is sufficient to see the issue.

array_bug-d57a78204f1529fa`array_bug::get::h8e3dc22d47c73cc1:
    0x1000014f0 <+0>:    pushq  %rbp
    0x1000014f1 <+1>:    movq   %rsp, %rbp
    0x1000014f4 <+4>:    movl   $0x2f9cd0, %eax           ; imm = 0x2F9CD0
    0x1000014f9 <+9>:    callq  0x10007fd40               ; __rust_probestack
    0x1000014fe <+14>:   subq   %rax, %rsp

As you can see, this function is trying to allocate 3120336 bytes on the stack.

A complete example from which the above output was derived is available here. The numbers in the array are meaningless. They came from /dev/urandom. The numbers in the match are likewise immaterial.

Meta

rustc --version --verbose:

rustc 1.49.0 (e1884a8e3 2020-12-29)
binary: rustc
commit-hash: e1884a8e3c3e813aada8254edfa120e85bf5ffca
commit-date: 2020-12-29
host: x86_64-apple-darwin
release: 1.49.0

The same occurs with nightly.

cargo 1.50.0-nightly (75d5d8cff 2020-12-22)
release: 1.50.0
commit-hash: 75d5d8cffe3464631f82dcd3c470b78dc1dda8bb
commit-date: 2020-12-22

RUST_BACKTRACE=1 does not work; however, here's a backtrace from rust-lldb.

Backtrace

* thread #2, name = 'test::test', stop reason = EXC_BAD_ACCESS (code=2, address=0x7000053986d8)
  * frame #0: 0x000000010007fd57 array_bug-d57a78204f1529fa`__rust_probestack + 23
    frame #1: 0x00000001000014fe array_bug-d57a78204f1529fa`array_bug::get::h8e3dc22d47c73cc1(idx=4294972670) at lib.rs:1
    frame #2: 0x00000001000032d2 array_bug-d57a78204f1529fa`array_bug::test::test::hc711f7a43c02bc30 at lib.rs:52:17
    frame #3: 0x0000000100004111 array_bug-d57a78204f1529fa`array_bug::test::test::_$u7b$$u7b$closure$u7d$$u7d$::had6d89fadeb77842((null)=0x0000700005598730) at lib.rs:51:5
    frame #4: 0x00000001000039f1 array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once::hc97ff02d53ad383b((null)=closure-0 @ 0x0000700005598730, (null)=<unavailable>) at function.rs:227:5
    frame #5: 0x000000010002c12a array_bug-d57a78204f1529fa`test::__rust_begin_short_backtrace::h1d6019f47cc55f08 [inlined] core::ops::function::FnOnce::call_once::h23ab09971f90347f at function.rs:227:5 [opt]
    frame #6: 0x000000010002c128 array_bug-d57a78204f1529fa`test::__rust_begin_short_backtrace::h1d6019f47cc55f08 at lib.rs:517 [opt]
    frame #7: 0x000000010002a8c7 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] _$LT$alloc..boxed..Box$LT$F$C$A$GT$$u20$as$u20$core..ops..function..FnOnce$LT$Args$GT$$GT$::call_once::h12a9510fad786d50 at boxed.rs:1307:9 [opt]
    frame #8: 0x000000010002a8c0 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] _$LT$std..panic..AssertUnwindSafe$LT$F$GT$$u20$as$u20$core..ops..function..FnOnce$LT$$LP$$RP$$GT$$GT$::call_once::ha48b56b04ad25da0 at panic.rs:322 [opt]
    frame #9: 0x000000010002a8c0 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] std::panicking::try::do_call::h4e253e91d72f4add at panicking.rs:381 [opt]
    frame #10: 0x000000010002a8c0 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] std::panicking::try::h04beadc619e361ca at panicking.rs:345 [opt]
    frame #11: 0x000000010002a8c0 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] std::panic::catch_unwind::hf3a82a81dfae044e at panic.rs:396 [opt]
    frame #12: 0x000000010002a8c0 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df [inlined] test::run_test_in_process::he5ca912ca9f4425d at lib.rs:544 [opt]
    frame #13: 0x000000010002a8a7 array_bug-d57a78204f1529fa`test::run_test::run_test_inner::_$u7b$$u7b$closure$u7d$$u7d$::h3defa140cc3517df at lib.rs:450 [opt]
    frame #14: 0x0000000100004e4b array_bug-d57a78204f1529fa`std::sys_common::backtrace::__rust_begin_short_backtrace::h11e8de6518e23f3b at backtrace.rs:125:18 [opt]
    frame #15: 0x000000010000a021 array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] std::thread::Builder::spawn_unchecked::_$u7b$$u7b$closure$u7d$$u7d$::_$u7b$$u7b$closure$u7d$$u7d$::hcfceb62bb517582f at mod.rs:474:17 [opt]
    frame #16: 0x0000000100009ffd array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] _$LT$std..panic..AssertUnwindSafe$LT$F$GT$$u20$as$u20$core..ops..function..FnOnce$LT$$LP$$RP$$GT$$GT$::call_once::h56a2e20a57edcf31 at panic.rs:322 [opt]
    frame #17: 0x0000000100009ffd array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] std::panicking::try::do_call::ha4b354535e898800 at panicking.rs:381 [opt]
    frame #18: 0x0000000100009ffd array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] std::panicking::try::hccd11140096bd12b at panicking.rs:345 [opt]
    frame #19: 0x0000000100009ffd array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] std::panic::catch_unwind::hf486f916485b6696 at panic.rs:396 [opt]
    frame #20: 0x0000000100009ffd array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 [inlined] std::thread::Builder::spawn_unchecked::_$u7b$$u7b$closure$u7d$$u7d$::hdb2f765d4cf1e663 at mod.rs:473 [opt]
    frame #21: 0x0000000100009f4d array_bug-d57a78204f1529fa`core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::h9c2b7019f7d7dd03 at function.rs:227 [opt]
    frame #22: 0x00000001000635ad array_bug-d57a78204f1529fa`std::sys::unix::thread::Thread::new::thread_start::hedb7cc0d930a8f40 [inlined] _$LT$alloc..boxed..Box$LT$F$C$A$GT$$u20$as$u20$core..ops..function..FnOnce$LT$Args$GT$$GT$::call_once::h22f4d58d7c8a821c at boxed.rs:1307:9 [opt]
    frame #23: 0x00000001000635a7 array_bug-d57a78204f1529fa`std::sys::unix::thread::Thread::new::thread_start::hedb7cc0d930a8f40 [inlined] _$LT$alloc..boxed..Box$LT$F$C$A$GT$$u20$as$u20$core..ops..function..FnOnce$LT$Args$GT$$GT$::call_once::haa812e1889643845 at boxed.rs:1307 [opt]
    frame #24: 0x000000010006359e array_bug-d57a78204f1529fa`std::sys::unix::thread::Thread::new::thread_start::hedb7cc0d930a8f40 at thread.rs:71 [opt]
    frame #25: 0x00007fff5ddb32eb libsystem_pthread.dylib`_pthread_body + 126
    frame #26: 0x00007fff5ddb6249 libsystem_pthread.dylib`_pthread_start + 66
    frame #27: 0x00007fff5ddb240d libsystem_pthread.dylib`thread_start + 13

[leonardo-m]

Thank you for reporting this.

[tesuji]

I think this is intentional. You could use static instead of const to move the array to ".rodata" section.
Maybe related to #73825.

[stevecheckoway]

static rather than const does indeed work.

It's very surprising to me that it would work this way. A clippy warning for this might be a good idea.

Should I close this issue?

[sfackler]

A const acts roughly like a #define, copying the value in place wherever the constant is used. When compiling with optimizations, the actual load of the array can be optimized out (and is in this case: https://rust.godbolt.org/z/Mje443), but that may not be the case for an unoptimized build.