Boxes with custom allocators break several underlying assumptions in Miri (and MIR more broadly)

[autumnontape]

This error got turned into a general design issue for Box as a language primitive vs Box having an 'allocator' field. See original bug report below. Also see a further testcase at rust-lang/miri#2072.

---

This is minimized from an error I ran into while implementing the Allocator API in my crate, bump-into, and trying to test the implementation with Miri:

Code

#![feature(allocator_api)]

extern crate alloc;

use alloc::alloc::{AllocError, Allocator};
use core::alloc::Layout;
use core::cell::Cell;
use core::mem::MaybeUninit;
use core::ptr::{self, NonNull};

struct OnceAlloc<'a> {
    space: Cell<&'a mut [MaybeUninit<u8>]>,
}

unsafe impl<'shared, 'a: 'shared> Allocator for &'shared OnceAlloc<'a> {
    fn allocate(&self, layout: Layout) -> Result<NonNull<[u8]>, AllocError> {
        let space = self.space.replace(&mut []);

        let (ptr, len) = (space.as_mut_ptr(), space.len());

        if ptr.align_offset(layout.align()) != 0 || len < layout.size() {
            return Err(AllocError);
        }

        let slice_ptr = ptr::slice_from_raw_parts_mut(ptr as *mut u8, len);
        unsafe { Ok(NonNull::new_unchecked(slice_ptr)) }
    }

    unsafe fn deallocate(&self, _ptr: NonNull<u8>, _layout: Layout) {}
}

fn main() {
    let mut space = vec![MaybeUninit::new(0); 1];
    let once_alloc = OnceAlloc {
        space: Cell::new(&mut space[..]),
    };

    let _boxed = Box::new_in([0u8; 1], &once_alloc);
}

Meta

rustc --version --verbose:

rustc 1.61.0-nightly (1d9c262ee 2022-03-26)
binary: rustc
commit-hash: 1d9c262eea411ec5230f8a4c9ba50b3647064da4
commit-date: 2022-03-26
host: x86_64-unknown-linux-gnu
release: 1.61.0-nightly
LLVM version: 14.0.0

Error output

$ env RUST_BACKTRACE=full cargo miri run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `/home/autumn/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri target/miri/x86_64-unknown-linux-gnu/debug/miri-ice`
error: internal compiler error: /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/compiler/rustc_const_eval/src/interpret/place.rs:777:26: write_immediate_to_mplace: invalid ScalarPair layout: TyAndLayout {
                                    ty: *mut [u8; 1],
                                    layout: Layout {
                                        fields: Primitive,
                                        variants: Single {
                                            index: 0,
                                        },
                                        abi: Scalar(
                                            Scalar {
                                                value: Pointer,
                                                valid_range: 0..=18446744073709551615,
                                            },
                                        ),
                                        largest_niche: None,
                                        align: AbiAndPrefAlign {
                                            abi: Align {
                                                pow2: 3,
                                            },
                                            pref: Align {
                                                pow2: 3,
                                            },
                                        },
                                        size: Size {
                                            raw: 8,
                                        },
                                    },
                                }
   --> /home/autumn/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:359:13
    |
359 |             boxed.as_mut_ptr().write(x);
    |             ^^^^^^^^^^^^^^^^^^

Backtrace

thread 'rustc' panicked at 'Box<dyn Any>', /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/compiler/rustc_errors/src/lib.rs:1222:9
stack backtrace:
   0:     0x7f4c0669d55d - std::backtrace_rs::backtrace::libunwind::trace::hb8664f5c920dcd17
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/../../backtrace/src/backtrace/libunwind.rs:93:5
   1:     0x7f4c0669d55d - std::backtrace_rs::backtrace::trace_unsynchronized::h4718639a025d9e7f
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/../../backtrace/src/backtrace/mod.rs:66:5
   2:     0x7f4c0669d55d - std::sys_common::backtrace::_print_fmt::h147f7c369d4f1e8e
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/sys_common/backtrace.rs:66:5
   3:     0x7f4c0669d55d - <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt::hee801905e555ec30
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/sys_common/backtrace.rs:45:22
   4:     0x7f4c066f755c - core::fmt::write::h4bb35aa347c570f4
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/core/src/fmt/mod.rs:1190:17
   5:     0x7f4c0668eab1 - std::io::Write::write_fmt::h6ed268cd0958975b
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/io/mod.rs:1655:15
   6:     0x7f4c066a0645 - std::sys_common::backtrace::_print::h3f974cf4bd76b112
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/sys_common/backtrace.rs:48:5
   7:     0x7f4c066a0645 - std::sys_common::backtrace::print::h56cc71e242d02ce1
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/sys_common/backtrace.rs:35:9
   8:     0x7f4c066a0645 - std::panicking::default_hook::{{closure}}::hca67c27c011873e3
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/panicking.rs:295:22
   9:     0x7f4c066a02f9 - std::panicking::default_hook::ha53803c35aaf5526
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/panicking.rs:314:9
  10:     0x7f4c06ece6c1 - rustc_driver[1cb8e757554a7e43]::DEFAULT_HOOK::{closure#0}::{closure#0}
  11:     0x7f4c066a0d90 - std::panicking::rust_panic_with_hook::hc072423965447af2
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/panicking.rs:702:17
  12:     0x5584173e5793 - std[907b070526960113]::panicking::begin_panic::<rustc_errors[f8e1677070e2f6d9]::ExplicitBug>::{closure#0}
  13:     0x5584173e5356 - std[907b070526960113]::sys_common::backtrace::__rust_end_short_backtrace::<std[907b070526960113]::panicking::begin_panic<rustc_errors[f8e1677070e2f6d9]::ExplicitBug>::{closure#0}, !>
  14:     0x55841725f996 - std[907b070526960113]::panicking::begin_panic::<rustc_errors[f8e1677070e2f6d9]::ExplicitBug>
  15:     0x558417309876 - std[907b070526960113]::panic::panic_any::<rustc_errors[f8e1677070e2f6d9]::ExplicitBug>
  16:     0x558417307f2a - <rustc_errors[f8e1677070e2f6d9]::HandlerInner>::span_bug::<rustc_span[c0544ac70c34a1b7]::span_encoding::Span>
  17:     0x558417307d70 - <rustc_errors[f8e1677070e2f6d9]::Handler>::span_bug::<rustc_span[c0544ac70c34a1b7]::span_encoding::Span>
  18:     0x558417312215 - rustc_middle[4fcaad924d73098a]::ty::context::tls::with_opt::<rustc_middle[4fcaad924d73098a]::util::bug::opt_span_bug_fmt<rustc_span[c0544ac70c34a1b7]::span_encoding::Span>::{closure#0}, ()>
  19:     0x558417311f69 - rustc_middle[4fcaad924d73098a]::util::bug::opt_span_bug_fmt::<rustc_span[c0544ac70c34a1b7]::span_encoding::Span>
  20:     0x55841725fa63 - rustc_middle[4fcaad924d73098a]::util::bug::span_bug_fmt::<rustc_span[c0544ac70c34a1b7]::span_encoding::Span>
  21:     0x558417350c5d - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::write_immediate_to_mplace_no_validate
  22:     0x55841734ff04 - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::write_immediate_no_validate
  23:     0x55841734f9c4 - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::copy_op_no_validate
  24:     0x55841734d4ba - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::copy_op_transmute
  25:     0x558417355324 - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::pop_stack_frame
  26:     0x558417342ddf - <rustc_const_eval[3ebf8ee4e08cef50]::interpret::eval_context::InterpCx<miri[17c863d3c0e6d9d6]::machine::Evaluator>>::terminator
  27:     0x5584172f42f0 - miri[17c863d3c0e6d9d6]::eval::eval_entry
  28:     0x558417265aec - <rustc_interface[38cec0579f964c4b]::passes::QueryContext>::enter::<<miri[f35c181d28723cbf]::MiriCompilerCalls as rustc_driver[1cb8e757554a7e43]::Callbacks>::after_analysis::{closure#0}, ()>
  29:     0x5584172637e5 - <miri[f35c181d28723cbf]::MiriCompilerCalls as rustc_driver[1cb8e757554a7e43]::Callbacks>::after_analysis
  30:     0x7f4c08d3e4b5 - <rustc_interface[38cec0579f964c4b]::interface::Compiler>::enter::<rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}::{closure#2}, core[69ec914610f0cf77]::result::Result<core[69ec914610f0cf77]::option::Option<rustc_interface[38cec0579f964c4b]::queries::Linker>, rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>
  31:     0x7f4c08d514bf - rustc_span[c0544ac70c34a1b7]::with_source_map::<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_interface[38cec0579f964c4b]::interface::create_compiler_and_run<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}>::{closure#1}>
  32:     0x7f4c08d3f114 - rustc_interface[38cec0579f964c4b]::interface::create_compiler_and_run::<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}>
  33:     0x7f4c08d3be92 - <scoped_tls[9467090f342ff13]::ScopedKey<rustc_span[c0544ac70c34a1b7]::SessionGlobals>>::set::<rustc_interface[38cec0579f964c4b]::interface::run_compiler<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}>::{closure#0}, core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>
  34:     0x7f4c08d3a1ff - std[907b070526960113]::sys_common::backtrace::__rust_begin_short_backtrace::<rustc_interface[38cec0579f964c4b]::util::run_in_thread_pool_with_globals<rustc_interface[38cec0579f964c4b]::interface::run_compiler<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}>::{closure#0}, core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>::{closure#0}, core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>
  35:     0x7f4c08d52452 - <<std[907b070526960113]::thread::Builder>::spawn_unchecked_<rustc_interface[38cec0579f964c4b]::util::run_in_thread_pool_with_globals<rustc_interface[38cec0579f964c4b]::interface::run_compiler<core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>, rustc_driver[1cb8e757554a7e43]::run_compiler::{closure#1}>::{closure#0}, core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>::{closure#0}, core[69ec914610f0cf77]::result::Result<(), rustc_errors[f8e1677070e2f6d9]::ErrorGuaranteed>>::{closure#1} as core[69ec914610f0cf77]::ops::function::FnOnce<()>>::call_once::{shim:vtable#0}
  36:     0x7f4c066aaf83 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::hf0cca23978c89840
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/alloc/src/boxed.rs:1861:9
  37:     0x7f4c066aaf83 - <alloc::boxed::Box<F,A> as core::ops::function::FnOnce<Args>>::call_once::h9da765b1ac504456
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/alloc/src/boxed.rs:1861:9
  38:     0x7f4c066aaf83 - std::sys::unix::thread::Thread::new::thread_start::hb3629e14c6b629e3
                               at /rustc/1d9c262eea411ec5230f8a4c9ba50b3647064da4/library/std/src/sys/unix/thread.rs:108:17
  39:     0x7f4c064835c2 - start_thread
  40:     0x7f4c06508584 - __clone
  41:                0x0 - <unknown>

[RalfJung]

Thanks for the report!

Something went very wrong a bit before this error occurred... a ScalarPair value should never have Scalar layout.

[matthiaskrgr]

smaller repro from glacier:

#![feature(allocator_api)]

fn main() {
    Box::new_in(&[0, 1], &std::alloc::Global);
}

[autumnontape]

@matthiaskrgr Indeed, I get a similar error when I run that code under Miri:

error: internal compiler error: /rustc/ec77f252434a532fdb5699ae4f21a3072d211edd/compiler/rustc_const_eval/src/interpret/place.rs:775:68: write_immediate_to_mplace: invalid ScalarPair layout: TyAndLayout {
                                    ty: *mut &[i32; 2],
                                    layout: Layout {
                                        fields: Primitive,
                                        variants: Single {
                                            index: 0,
                                        },
                                        abi: Scalar(
                                            Initialized {
                                                value: Pointer,
                                                valid_range: 0..=18446744073709551615,
                                            },
                                        ),
                                        largest_niche: None,
                                        align: AbiAndPrefAlign {
                                            abi: Align {
                                                pow2: 3,
                                            },
                                            pref: Align {
                                                pow2: 3,
                                            },
                                        },
                                        size: Size {
                                            raw: 8,
                                        },
                                    },
                                }
   --> /home/autumn/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/alloc/src/boxed.rs:363:13
    |
363 |             boxed.as_mut_ptr().write(x);
    |             ^^^^^^^^^^^^^^^^^^

This is with the latest nightly:

$ rustc --version --verbose
rustc 1.62.0-nightly (ec77f2524 2022-04-17)
binary: rustc
commit-hash: ec77f252434a532fdb5699ae4f21a3072d211edd
commit-date: 2022-04-17
host: x86_64-unknown-linux-gnu
release: 1.62.0-nightly
LLVM version: 14.0.0

But that ICE is marked as fixed. Should this be closed as a duplicate and #78459 reopened?

[RalfJung]

#78459 was fixed by doing something in the codegen backend, this here is about the interpreter. It think it is a separate, albeit related, problem.

[autumnontape]

I see, that explains why it wasn't caught as a regression.

[RalfJung]

I suspect this has something to do with dereferencing a Box. It looks like even Box<_, Alloc> are considered primitive pointers that can be dereferenced, which somehow has to implicitly throw away the allocation part? There is no indication in the MIR that anything like that is happening, so each backend has to do it separately.

Honestly that sounds like a pretty bad way to encode this all. The way allocators were added to Box broke a fundamental assumption that Miri (and probably plenty of other MIR consumers) made: if builtin_deref succeeds on a value of a given type (aka if we can have *ptr in MIR on a value of that type), then that value is a pointer (and just a pointer, not a pointer-allocator pair). Now instead all MIR consumers have to be wary each time they use a "pointer" (i.e., something where *ptr works) because that "pointer" might be arbitrarily complex data where we first have to dig for the actual pointer part in it. We can keep putting ad-hoc fixes for this everywhere but I can almost guarantee this is going to create a constant stream of issues.

Cc @rust-lang/wg-mir-opt (there is no WG-MIR I think?) @rust-lang/wg-allocators

[RalfJung]

Here's a way to cause even more fun ICEs in Miri, by making Box<T, G> so big that it cannot be represented as an 'immediate' any more. Interestingly this works in codegen, I guess it must be littered with special cases that treat Box pointers different than any other pointer -- not sure if there is another way to do that.

And indeed, we have

rust/compiler/rustc_codegen_ssa/src/mir/operand.rs

Line 131 in d32ce37

if self.layout.ty.is_box() && !self.layout.field(cx, 1).is_zst() {

rust/compiler/rustc_codegen_ssa/src/mir/place.rs

Line 450 in c58af72

if cg_base.layout.ty.is_box() && !cg_base.layout.field(cx, 1).is_zst() {

rust/compiler/rustc_codegen_ssa/src/mir/place.rs

Line 468 in c58af72

if cg_base.layout.ty.is_box() && !cg_base.layout.field(cx, 1).is_zst() {

rust/compiler/rustc_codegen_llvm/src/debuginfo/metadata.rs

Line 454 in e169261

ty::Adt(def, substs) if def.is_box() && cx.layout_of(substs.type_at(1)).is_zst() => {

rust/compiler/rustc_codegen_llvm/src/type_of.rs

Line 343 in d32ce37

ty::Adt(def, substs) if def.is_box() && cx.layout_of(substs.type_at(1)).is_zst() => {

[CAD97]

"Box is a special type kind" strikes again...

The proper fix-for-all-time is to stop making Box special, and for it to just be a regular aggregate and DerefMove or whatever you want to call it specify the special behavior where the deref place is managed kinda like a local.

How practical that is in the short/medium term, though, is a different question. However, it's probably required to let Box use the theoretical storage API (as inline storage isn't even a pointer anymore), and might be simpler than compounding special cases even more...

[RalfJung]

I got things to work for the example, and for a nasty variant of the example that makes Box not even a ScalarPair type any more:

• interpret: handle Box with non-ZST allocator #96198
• tests for Box with non-ZST allocator miri#2072

As you can see, various random places throughout the interpreter need to be aware of this -- the hallmark of non-compositional design. Stacked Borrows will ignore such Boxes (so if they are noalias, this will miss UB) and validity checking will not complain when they fail to be dereferencable. Basically Box with non-ZST allocator is treated like a regular user type that somehow magically can have the * operator applied to it, but has none of the other Box magic. (I don't know if we generate LLVM attributes like noalias for such boxes; if we do, that'd be even worse since Miri would not be able to check that.)

Also, this does not entirely fix the problem; this example still ICEs because the casting and unsizing code assumes that it will only be called with regular pointer types. I've run out of steam for fixing that; it would probably require special treatment around here. There are probably more places I missed, it is very hard to be sure since this is breaking some very fundamental assumptions.