fastalloc does not support arbitrary numbers of `any` defs allocating into spillslots

[cfallin]

After bytecodealliance/wasmtime#10502, a necessary prerequisite for exception handling in Cranelift (and thus Wasmtime), we generate all return-value defs for callsites as defs on the call instruction, with an any constraint. The default (backtracking) allocator is able to allocate defs past the number of registers into spillslots directly. However, it appears that fastalloc cannot do this: it aborts if a def with an any constraint cannot allocate a register.

See this fuzzbug for a reproduction.

[cfallin]

I'm filing this as a tracking issue and will disable fastalloc in Cranelift for now; it's a tier-3 feature and I don't have the cycles to update the allocator unfortunately. At some later time we may be able to fix this limitation and then re-enable it.

[d-sonuga]

Hey @cfallin, is this the same bug?

thread '<unnamed>' panicked at /Users/d-sonuga/repos/regalloc2/src/fastalloc/mod.rs:154:56:
called `Option::unwrap()` on a `None` value
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
==86022== ERROR: libFuzzer: deadly signal
    #0 0x00010723dcc0 in __sanitizer_print_stack_trace+0x28 (librustc-nightly_rt.asan.dylib:arm64+0x5dcc0)
    #1 0x000105a9eef0 in fuzzer::PrintStackTrace()+0x30 (fastalloc_checker:arm64+0x101006ef0)
    #2 0x000105a92154 in fuzzer::Fuzzer::CrashCallback()+0x54 (fastalloc_checker:arm64+0x100ffa154)
    #3 0x0001837b8620 in _sigtramp+0x34 (libsystem_platform.dylib:arm64+0x3620)
    #4 0x00018377e888 in pthread_kill+0x124 (libsystem_pthread.dylib:arm64+0x6888)
    #5 0x000183687c5c in abort+0x78 (libsystem_c.dylib:arm64+0x78c5c)
    #6 0x000105be42c8 in std::sys::pal::unix::abort_internal::hc6a174fee9c4fd65+0x8 (fastalloc_checker:arm64+0x10114c2c8)
    #7 0x000105be34ac in std::process::abort::he28388c695e4448f+0x8 (fastalloc_checker:arm64+0x10114b4ac)
    #8 0x000105bdd140 in libfuzzer_sys::initialize::_$u7b$$u7b$closure$u7d$$u7d$::h4f87efe0271793cf+0xb8 (fastalloc_checker:arm64+0x101145140)
    #9 0x000105b5e8e4 in std::panicking::rust_panic_with_hook::h9ef2e9be5a60c77d+0x258 (fastalloc_checker:arm64+0x1010c68e4)
    #10 0x000105b5e4b4 in std::panicking::begin_panic_handler::_$u7b$$u7b$closure$u7d$$u7d$::h2df1fe502626d25a+0x64 (fastalloc_checker:arm64+0x1010c64b4)
    #11 0x000105b5ac2c in std::sys::backtrace::__rust_end_short_backtrace::h9dbc61b2803803db+0x8 (fastalloc_checker:arm64+0x1010c2c2c)
    #12 0x000105b5e1b8 in _RNvCsjg72BucUYAS_7___rustc17rust_begin_unwind+0x1c (fastalloc_checker:arm64+0x1010c61b8)
    #13 0x000105be5368 in core::panicking::panic_fmt::h4f6ddc85c9a2252a+0x1c (fastalloc_checker:arm64+0x10114d368)
    #14 0x000105be53c4 in core::panicking::panic::hc95748aff40ab408+0x30 (fastalloc_checker:arm64+0x10114d3c4)
    #15 0x000105be5300 in core::option::unwrap_failed::hd782f17fdc2aa72b+0x18 (fastalloc_checker:arm64+0x10114d300)
    #16 0x0001059efdb4 in regalloc2::fastalloc::Edits::add_move::he5c56844f4b5c1f8+0x1158 (fastalloc_checker:arm64+0x100f57db4)
    #17 0x000104ba7b30 in regalloc2::fastalloc::Env$LT$F$GT$::alloc_inst::he89438cd558bcebc mod.rs:977
    #18 0x000104baa85c in regalloc2::fastalloc::Env$LT$F$GT$::alloc_block::h8785073e80875e68 mod.rs:1205
    #19 0x000104bcbf1c in regalloc2::fastalloc::Env$LT$F$GT$::run::ha61fe3d6f5364637 mod.rs:1227
    #20 0x000104bcf644 in regalloc2::fastalloc::run::h08c76aa3245949b6 mod.rs:1298
    #21 0x000104bd34bc in fastalloc_checker::_::__libfuzzer_sys_run::h7c540aaf859a2e4a fastalloc_checker.rs:41
    #22 0x000104bd2a50 in rust_fuzzer_test_input lib.rs:359
    #23 0x000105a8ca08 in std::panicking::catch_unwind::do_call::h5889860c969079c3+0x1c0 (fastalloc_checker:arm64+0x100ff4a08)
    #24 0x000105a913b4 in __rust_try+0x18 (fastalloc_checker:arm64+0x100ff93b4)
    #25 0x000105a9068c in LLVMFuzzerTestOneInput+0x16c (fastalloc_checker:arm64+0x100ff868c)
    #26 0x000105a93a4c in fuzzer::Fuzzer::ExecuteCallback(unsigned char const*, unsigned long)+0x150 (fastalloc_checker:arm64+0x100ffba4c)
    #27 0x000105a930e0 in fuzzer::Fuzzer::RunOne(unsigned char const*, unsigned long, bool, fuzzer::InputInfo*, bool, bool*)+0x48 (fastalloc_checker:arm64+0x100ffb0e0)
    #28 0x000105a94b48 in fuzzer::Fuzzer::MutateAndTestOne()+0x234 (fastalloc_checker:arm64+0x100ffcb48)
    #29 0x000105a95948 in fuzzer::Fuzzer::Loop(std::__1::vector<fuzzer::SizedFile, std::__1::allocator<fuzzer::SizedFile>>&)+0x358 (fastalloc_checker:arm64+0x100ffd948)
    #30 0x000105ab6148 in fuzzer::FuzzerDriver(int*, char***, int (*)(unsigned char const*, unsigned long))+0x1c30 (fastalloc_checker:arm64+0x10101e148)
    #31 0x000105ac3b00 in main+0x24 (fastalloc_checker:arm64+0x10102bb00)
    #32 0x0001833deb94 in start+0x17b8 (dyld:arm64+0xfffffffffff3ab94)

NOTE: libFuzzer has rudimentary signal handlers.
      Combine libFuzzer with AddressSanitizer or similar for better crash reports.
SUMMARY: libFuzzer: deadly signal
MS: 3 CopyPart-ChangeBit-EraseBytes-; base unit: 871afa9ecd8c5179dfa37f6344d2bd0e9c7133bd
artifact_prefix='/Users/d-sonuga/repos/regalloc2/fuzz/artifacts/fastalloc_checker/'; Test unit written to /Users/d-sonuga/repos/regalloc2/fuzz/artifacts/fastalloc_checker/crash-35feaf3e379eef544f51c0803d72611ca5a77c63
stat::number_of_executed_units: 5521
stat::average_exec_per_sec:     197
stat::new_units_added:          0
stat::slowest_unit_time_sec:    0
stat::peak_rss_mb:              854

────────────────────────────────────────────────────────────────────────────────

Failing input:

        fuzz/artifacts/fastalloc_checker/crash-35feaf3e379eef544f51c0803d72611ca5a77c63

Output of `std::fmt::Debug`:

        TestCase {
            func: {
              block0(): # succs:[] preds:[]
                inst0: Op ops:[Def: v0i any] clobber:[]
                inst1: Op ops:[Def@Early: v1v fixed(p10v), Use: v0i reg, Use: v0i reg, Use: v0i fixed(p39i), Use: v0i fixed(p49i), Use: v0i any, Use: v0i reg, Use: v0i reg, Use: v0i reg, Use: v0i reg, Use: v0i fixed(p45i)] clobber:[]
                inst2: Op ops:[Def@Early: v2f reg, Use: v1v any, Use: v1v reg, Use: v1v reg, Use: v1v reg] clobber:[]
                inst3: Op ops:[Def: v3v reg, Use: v2f reg, Use: v2f reg, Use: v2f reg, Use: v1v reg, Use: v0i reg] clobber:[]
                inst4: Op ops:[Def@Early: v4f reg, Use: v3v fixed(p3v), Use: v3v any, Def: v14i any, Def: v15i any, Def: v16i any] clobber:[PReg(hw = 7, class = Int, index = 7), PReg(hw = 7, class = Int, index = 7)]
                inst5: Op ops:[Def@Early: v5v reg, Use: v0i reg, Use: v0i reg, Use: v3v reg, Use: v0i any, Use: v4f reg, Use: v0i any, Use: v0i any, Use: v0i reg, Use: v4f reg, Use: v0i any] clobber:[]
                inst6: Op ops:[Def: v6v reuse(5), Use: v5v reg, Use: v5v any, Use: v0i reg, Use: v5v reg, Use: v5v reg, Use: v5v reg, Use: v3v any, Use: v1v any, Use: v3v reg, Use: v5v reg] clobber:[]
                inst7: Op ops:[Def: v7v reuse(2), Use: v1v any, Use: v3v reg, Use: v2f reg, Use: v2f reg] clobber:[]
                inst8: Op ops:[Def: v8v reuse(6), Use: v1v reg, Use: v1v reg, Use: v3v reg, Use: v1v reg, Use: v1v reg, Use: v1v reg, Use: v0i any, Use: v0i any, Use: v0i any, Use: v0i reg] clobber:[]
                inst9: Op ops:[Def@Early: v9v reg, Use: v6v fixed(p35v), Use: v0i fixed(p35i), Use: v3v reg, Use: v3v reg, Use: v3v reg, Use: v3v reg, Use: v3v reg, Use: v3v reg, Use: v3v reg, Use: v3v fixed(p7v), Def: v17v any, Def: v18v any, Def: v19v any, Def: v20i any, Def: v21i any, Def: v22i any, Def: v23i any, Def: v24i any, Def: v25v any, Def: v26v any, Def: v27v any, Def: v28v any, Def: v29v any, Def: v30v any] clobber:[PReg(hw = 4, class = Vector, index = 132), PReg(hw = 4, class = Vector, index = 132)]
                inst10: Op ops:[Def: v10v reg] clobber:[PReg(hw = 3, class = Vector, index = 131), PReg(hw = 16, class = Float, index = 80), PReg(hw = 28, class = Int, index = 28), PReg(hw = 4, class = Vector, index = 132), PReg(hw = 0, class = Float, index = 64)]
                inst11: Op ops:[Def@Early: v11i reg, Use: v10v reg, Use: v1v any] clobber:[]
                inst12: Op ops:[Def@Early: v12i reg, Use: v5v any, Use: v5v reg, Use: v5v reg, Use: v5v reg, Use: v5v reg, Use: v0i fixed(p4i), Use: v5v reg, Use: v5v reg, Use: v5v reg, Use: v5v fixed(p2v), Def: v31f any, Def: v32v any, Def: v33i any, Def: v34f any, Def: v35v any, Def: v36v any, Def: v37v any, Def: v38v any, Def: v39v any, Def: v40v any, Def: v41v any, Def: v42v any, Def: v43v any, Def: v44v any, Def: v45v any, Def: v46v any, Def: v47v any, Def: v48v any] clobber:[PReg(hw = 3, class = Vector, index = 131)]
                inst13: Op ops:[Def: v13i reuse(6), Use: v0i any, Use: v0i any, Use: v0i any, Use: v0i any, Use: v0i reg, Use: v0i reg, Use: v0i reg, Use: v0i reg, Use: v6v any, Use: v6v reg] clobber:[]
                inst14: Ret ops:[] clobber:[]
            }
            ,
        }

Reproduce with:

        cargo fuzz run fastalloc_checker fuzz/artifacts/fastalloc_checker/crash-35feaf3e379eef544f51c0803d72611ca5a77c63

Minimize test case with:

        cargo fuzz tmin fastalloc_checker fuzz/artifacts/fastalloc_checker/crash-35feaf3e379eef544f51c0803d72611ca5a77c63

────────────────────────────────────────────────────────────────────────────────

I just got this while running the fuzzer yesterday.

[cfallin]

@d-sonuga I'm not sure -- that looks more like an issue with lack of a scratch register (the unwrap that fails is here I think?), but could be caused by too many defs occupying all registers. You might be able to reproduce the exact issue by re-enabling the fastalloc algorithm in Cranelift and then running Wasmtime with a Wasm input that has a function returning many return values (say, 100)?