ReadBytesAsPointer error in std::collections::BTreeSet

[dwrensha]

Consider the following program:

// debug_miri.rs

#[derive(PartialEq, Eq, PartialOrd, Ord)]
pub enum Foo {
    A(&'static str),
    _B,
    _C,
}

pub fn main() {
    let mut b = std::collections::BTreeSet::new();
    b.insert(Foo::A("\'"));
    b.insert(Foo::A("/="));
    b.insert(Foo::A("#"));
    b.insert(Foo::A("0o"));
}

When I compile this program with rustc, the resulting executable runs and exits successfully. When I run the executable under valgrind, no errors are reported. When I run it with miri, I expect it to succeed, but it does not. Instead, it reports a ReadBytesAsPointer error:

$ RUST_BACKTRACE=1 cargo run --bin miri -- debug_miri.rs 
    Finished dev [unoptimized + debuginfo] target(s) in 0.0 secs
     Running `target/debug/miri debug_miri.rs`
ERROR:rustc_miri::interpret::eval_context: 

An error occurred in miri:
2: rustc_miri::interpret::error::{{impl}}::from
        at src/librustc_mir/interpret/error.rs:24
3: core::convert::{{impl}}::into<rustc_miri::interpret::error::EvalErrorKind,rustc_miri::interpret::error::EvalError>
        at /checkout/src/libcore/convert.rs:398
4: rustc_miri::interpret::value::{{impl}}::to_ptr
        at src/librustc_mir/interpret/value.rs:278
5: rustc_miri::interpret::value::{{impl}}::to_ptr
        at src/librustc_mir/interpret/value.rs:56
6: rustc_miri::interpret::memory::{{impl}}::read_bytes<miri::Evaluator>
        at /home/dwrensha/src/miri/src/librustc_mir/interpret/memory.rs:1146
7: miri::fn_call::{{impl}}::call_c_abi
        at miri/fn_call.rs:207
8: miri::fn_call::{{impl}}::call_missing_fn
        at miri/fn_call.rs:538
9: miri::fn_call::{{impl}}::eval_fn_call
        at miri/fn_call.rs:63
10: miri::{{impl}}::eval_fn_call
        at miri/lib.rs:188
11: rustc_miri::interpret::terminator::{{impl}}::eval_fn_call<miri::Evaluator>
        at /home/dwrensha/src/miri/src/librustc_mir/interpret/terminator/mod.rs:300
12: rustc_miri::interpret::terminator::{{impl}}::eval_terminator<miri::Evaluator>
        at /home/dwrensha/src/miri/src/librustc_mir/interpret/terminator/mod.rs:101
13: rustc_miri::interpret::step::{{impl}}::terminator<miri::Evaluator>
        at /home/dwrensha/src/miri/src/librustc_mir/interpret/step.rs:200
14: rustc_miri::interpret::step::{{impl}}::step<miri::Evaluator>
        at /home/dwrensha/src/miri/src/librustc_mir/interpret/step.rs:85
15: miri::eval_main::run_main
        at miri/lib.rs:123
16: miri::eval_main
        at miri/lib.rs:136

error: a memory access tried to interpret some bytes as a pointer
     |
note: inside call to <[u8] as core::slice::SliceOrd<u8>>::compare
note: inside call to core::slice::<impl std::cmp::Ord for [T]><u8>::cmp
note: inside call to core::str::traits::<impl std::cmp::Ord for str>::cmp
note: inside call to std::cmp::impls::<impl std::cmp::Ord for &'a A><str>::cmp
    --> debug_miri.rs:5:7
     |
5    |     A(&'static str),
     |       ^^^^^^^^^^^^^
note: inside call to <Foo as std::cmp::Ord>::cmp
note: inside call to alloc::btree::search::search_linear::<alloc::btree::node::marker::Mut, Foo, (), alloc::btree::node::marker::LeafOrInternal, Foo>
note: inside call to alloc::btree::search::search_node::<alloc::btree::node::marker::Mut, Foo, (), alloc::btree::node::marker::LeafOrInternal, Foo>
note: inside call to alloc::btree::search::search_tree::<alloc::btree::node::marker::Mut, Foo, (), Foo>
note: inside call to <std::collections::BTreeMap<K, V>><Foo, ()>::entry
note: inside call to <std::collections::BTreeMap<K, V>><Foo, ()>::insert
note: inside call to <std::collections::BTreeSet<T>><Foo>::insert
    --> debug_miri.rs:15:5
     |
15   |     b.insert(Foo::A("0o"));
     |     ^^^^^^^^^^^^^^^^^^^^^^
note: inside call to main
    --> debug_miri.rs:10:1
     |
10   | / pub fn main() {
11   | |     let mut b = std::collections::BTreeSet::new();
12   | |     b.insert(Foo::A("\'"));
13   | |     b.insert(Foo::A("/="));
14   | |     b.insert(Foo::A("#"));
15   | |     b.insert(Foo::A("0o"));
16   | | }
     | |_^

error: aborting due to previous error

thread 'main' panicked at 'Box<Any>', /checkout/src/librustc_errors/lib.rs:529:8
stack backtrace:
   0: std::sys::imp::backtrace::tracing::imp::unwind_backtrace
             at /checkout/src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::_print
             at /checkout/src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at /checkout/src/libstd/sys_common/backtrace.rs:60
             at /checkout/src/libstd/panicking.rs:381
   3: std::panicking::default_hook
             at /checkout/src/libstd/panicking.rs:397
   4: std::panicking::rust_panic_with_hook
             at /checkout/src/libstd/panicking.rs:611
   5: std::panicking::begin_panic
   6: rustc_errors::Handler::abort_if_errors
   7: miri::after_analysis
             at miri/bin/miri.rs:139
   8: core::ops::function::Fn::call
             at /checkout/src/libcore/ops/function.rs:73
   9: rustc_driver::driver::compile_input::{{closure}}
  10: rustc::ty::context::TyCtxt::create_and_enter
  11: rustc_driver::driver::compile_input
  12: rustc_driver::run_compiler
  13: miri::main
             at miri/bin/miri.rs:258
  14: __rust_maybe_catch_panic
             at /checkout/src/libpanic_unwind/lib.rs:98
  15: std::rt::lang_start
             at /checkout/src/libstd/panicking.rs:459
             at /checkout/src/libstd/panic.rs:361
             at /checkout/src/libstd/rt.rs:61
  16: main
  17: __libc_start_main
  18: _start

[RalfJung]

It is a known problem that miri's handling of pointers is incomplete and cannot handle everything that is safe in Rust. (Some of the things that are safe IMHO shouldn't be because this is not just a superficial problem, but that ship has sailed.)

See #224 and in particular #224 (comment) for some more information about this. I had hoped to write the first of two blog posts on this by now, but that didn't happen -- but I still plan to come back to this, after my vacation.

[RalfJung]

That said, this incompleteness usually results in the "opposite" error (cannot turn pointer into bytes). This one looks different. Not sure what is going on.

[dwrensha]

The error gets thrown when memcmp(left, right, n) gets called with right equal to ByVal(Bytes(0)). To me, this seems like a symptom of corrupted memory. My wild guess is that there are some stray writes in glue code somewhere.

[dwrensha]

I've reduced to a much smaller test case, updating my first comment above.

[oli-obk]

I think I found the bug. Memory::copy doesn't copy relocations correctly if the copy memory is overlapping.

The issue is that we erase the relocations while we copy bytes. So when we try to copy the relocations in the next step, they are already gone in the overlapping memory.

[dwrensha]

Awesome!