Issues running tests in miri

[jamesmunns]

Hey! I'm building a sort of "liballoc replacement" for my work on MnemOS, and I'm both using linked_list_allocator, and doing some pretty gnarly unsafe stuff on top of it. Because of this, I wanted to get miri testing going to make sure I am not shooting myself in the foot, but it seems pretty upset about linked_list_allocator in general.

Even without the newer strict provenance checks, I'm getting errors like this just constructing the heap in the tests:

$ cargo +nightly miri test
...
test test::oom ... error: Undefined Behavior: not granting access to tag <untagged> because incompatible item is protected: [Unique for <189711> (call 54826)]
    --> /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1342:9
     |
1342 | ...   copy_nonoverlapping(&src as *const T, dst, 1);
     |       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ not granting access to tag <untagged> because incompatible item is protected: [Unique for <189711> (call 54826)]
     |
     = help: this indicates a potential bug in the program: it performed an invalid operation, but the rules it violated are still experimental
     = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: tag was most recently created at offsets [0x0..0x3e8]
    --> src/lib.rs:126:23
     |
126  |         let address = mem.as_ptr() as usize;
     |                       ^^^^^^^^^^^^
help: tag was later invalidated at offsets [0x6..0x16]
    --> src/hole.rs:50:9
     |
50   | / ...   ptr.write(Hole {
51   | | ...       size: hole_size.saturating_sub(aligned...
52   | | ...       next: None,
53   | | ...   });
     | |________^
help: this tag was also created here at offsets [0x0..0x3e8]
    --> src/lib.rs:125:20
     |
125  |         let size = mem.len();
     |                    ^^^^^^^^^
help: <189707> was protected due to a tag which was created here
    --> src/test.rs:11:33
     |
11   |     let heap = Heap::from_slice(heap_space);
     |                                 ^^^^^^^^^^
help: this protector is live for this call
    --> src/lib.rs:124:5
     |
124  | /     pub fn from_slice(mem: &'static mut [MaybeUn...
125  | |         let size = mem.len();
126  | |         let address = mem.as_ptr() as usize;
127  | |         // SAFETY: The given address and size is...
128  | |         // mutable reference handed to us by the...
129  | |         unsafe { Self::new(address, size) }
130  | |     }
     | |_____^
     = note: inside `core::ptr::write::<hole::Hole>` at /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:1342:9
     = note: inside `core::ptr::mut_ptr::<impl *mut hole::Hole>::write` at /home/james/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mut_ptr.rs:1406:18
note: inside `hole::HoleList::new` at src/hole.rs:50:9
    --> src/hole.rs:50:9
     |
50   | / ...   ptr.write(Hole {
51   | | ...       size: hole_size.saturating_sub(aligned...
52   | | ...       next: None,
53   | | ...   });
     | |________^
note: inside `Heap::new` at src/lib.rs:115:24
    --> src/lib.rs:115:24
     |
115  | ...les: HoleList::new(heap_bottom, heap_size),
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `Heap::from_slice` at src/lib.rs:129:18
    --> src/lib.rs:129:18
     |
129  |         unsafe { Self::new(address, size) }
     |                  ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `test::new_heap` at src/test.rs:11:16
    --> src/test.rs:11:16
     |
11   |     let heap = Heap::from_slice(heap_space);
     |                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `test::oom` at src/test.rs:39:20
    --> src/test.rs:39:20
     |
39   |     let mut heap = new_heap();
     |                    ^^^^^^^^^^
note: inside closure at src/test.rs:38:1
    --> src/test.rs:38:1
     |
37   |   #[test]
     |   ------- in this procedural macro expansion
38   | / fn oom() {
39   | |     let mut heap = new_heap();
40   | |     // let layout = Layout::from_size_align(heap...
41   | |     // let addr = heap.allocate_first_fit(layout...
42   | |     // assert!(addr.is_err());
43   | | }
     | |_^
     = note: this error originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error; 5 warnings emitted

error: test failed, to rerun pass '--lib'

This seems pretty challenging to deal with: Miri is complaining that the allocator is holding a pointer with provenance to the entire range, and that writing the first Hole in that range is invalidating the tag.

I saw that you and @HeroicKatora had done some work to make miri happy in the past, I'm not sure if this has changed due to certain behaviors becoming defaults (stacked borrows maybe?).

I'd be happy to help getting these passing again if I can!

[jamesmunns]

I had a chat with Oli on Zulip, and he suggested a couple things to try. I'll give it a hack this evening, unless y'all have any silver bullet ideas :D

[phil-opp]

Hi @jamesmunns, thanks a lot for raising this issue! I agree that miri checks would be quite useful for this crate, especially with the proposed strict provenance rules.

Right now, I think the main problem is that we're using usize for storing addresses, as mentioned in #55 (comment). I just tried to replace usize with *mut u8 in most places and it seems to improve things. Now the following error occurs:

test test::allocate_and_free_double_usize ... error: Undefined Behavior: accessing memory with alignment 2, but alignment 8 is required
  --> src/test.rs:76:9
   |
76 |         assert_eq!((*(heap.bottom as *const Hole)).size, heap.size);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ accessing memory with alignment 2, but alignment 8 is required
   |
   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information
           
   = note: inside `test::allocate_and_free_double_usize` at /home/philipp/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/macros/mod.rs:38:16

If I comment out the allocate_and_free_double_usize test, I don't get any errors from miri anymore, but multiple tests fail:

running 14 tests
test test::align_from_small_to_big ... ok
test test::allocate_double_usize ... FAILED
test test::allocate_multiple_sizes ... ok
test test::allocate_usize ... ok
test test::allocate_usize_in_bigger_block ... ok
test test::deallocate_middle ... FAILED
test test::deallocate_right_before ... FAILED
test test::deallocate_right_behind ... FAILED
test test::empty ... ok
test test::extend_empty_heap ... FAILED
test test::extend_fragmented_heap ... FAILED
test test::extend_full_heap ... FAILED
test test::oom ... ok
test test::reallocate_double_usize ... ok

failures:

---- test::allocate_double_usize stdout ----
thread 'main' panicked at 'assertion failed: addr == heap.bottom', src/test.rs:53:5
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

---- test::deallocate_middle stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `999`,
 right: `1000`', src/test.rs:140:9

---- test::deallocate_right_before stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `993`,
 right: `1000`', src/test.rs:96:9

---- test::deallocate_right_behind stdout ----
thread 'main' panicked at 'assertion failed: `(left == right)`
  left: `998`,
 right: `1000`', src/test.rs:116:9

---- test::extend_empty_heap stdout ----
thread 'main' panicked at 'assertion failed: heap.allocate_first_fit(layout.clone()).is_ok()', src/test.rs:253:5

---- test::extend_fragmented_heap stdout ----
thread 'main' panicked at 'assertion failed: alloc2.is_ok()', src/test.rs:281:5

---- test::extend_full_heap stdout ----
thread 'main' panicked at 'assertion failed: heap.allocate_first_fit(layout.clone()).is_ok()', src/test.rs:263:5

I'm not sure what's causing this, but it's probably an indication for some undefined behavior. Without miri, all the tests still pass. I try to investigate this further when I have some time.

[197g]

I can't add too much, only vague memory, but my work on miri was concentrated on a single code path. Many other tests may still have failed MIRI even at that time and due what I assumed to be false positives (?) from manual alignment stricter than allocation alignments, I didn't have an incentive to look too deeply. Just attributed them to known issues, waiting for symbolic execution of address calculations to resolve these at some point in MIRI (align_to can't be used internally so the current -Zmiri-symbolic-alignment-check checks are insufficiently strict).

[jamesmunns]

Thanks to both of you! After posting this I promptly got sick, but do hope to hack on this soon. I'll take a look at your Miri branch - replacing the usizes was where Oli suggested to start.

I'll report back if I make any headway!

[jamesmunns]

Following up on this in #62