Miri UB with -Zmiri-track-raw-pointers

[pandaman64]

Hi! I got UB when running Miri with raw pointer tracking enabled (-Zmiri-track-raw-pointers) against the invocation of GreenNodeBuilder::token. The UB is not reported when running Miri without raw pointer tracking.
To reproduce the UB, run the following function with MIRIFLAGS='-Zmiri-track-raw-pointers' cargo +nightly miri run.

use rowan::{GreenNodeBuilder, SyntaxKind};

fn main() {
    let mut builder = GreenNodeBuilder::new();
    builder.start_node(SyntaxKind(0));
    builder.token(SyntaxKind(1), "foo");
}

Here is the backtrace:

error: Undefined Behavior: no item granting write access to tag <3629> at alloc1681+0x18 found in borrow stack.
   --> /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    |
887 |         copy_nonoverlapping(&src as *const T, dst, 1);
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting write access to tag <3629> at alloc1681+0x18 found in borrow stack.
    |
    = 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
            
    = note: inside `std::ptr::write::<u8>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:887:9
    = note: inside `rowan::arc::ThinArc::<rowan::green::token::GreenTokenHead, u8>::from_header_and_iter::<std::str::Bytes>` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.12.6/src/arc.rs:382:21
    = note: inside `rowan::GreenToken::new` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.12.6/src/green/token.rs:110:19
    = note: inside `rowan::green::builder::NodeCache::token` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.12.6/src/green/builder.rs:93:29
    = note: inside `rowan::GreenNodeBuilder::token` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.12.6/src/green/builder.rs:133:29
note: inside `main` at src/main.rs:5:5
   --> src/main.rs:5:5
    |
5   |     builder.token(SyntaxKind(1), "foo");
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:63:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside closure at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:48
    = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside `std::rt::lang_start_internal` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:20
    = note: inside `std::rt::lang_start::<()>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:62:5

error: aborting due to previous error

It looks like Miri is not satisfied with ThinArc construction.

[CAD97]

I believe this is rust-lang/unsafe-code-guidelines#134 / rust-lang/unsafe-code-guidelines#256 / rust-lang/unsafe-code-guidelines#276.

The short version is that ThinArc stores and works with *mut ArcInner<HeaderSlice<H, [T; 0]>> but uses it as *mut ArcInner<HeaderSlice<H, [T; {length}]>>. This might be fixable with some judicious use of ptr::addr_of_mut!, or it might require more type erasure a la https://lib.rs/crates/erasable.

Taking a glance at the code, though, there are definitely a number of places that need to use ptr::addr_of_mut! to avoid creating references to uninitialized memory, though; I'll run through and do some first-pass cleanup today or tomorrow.

EDIT: the only computer I have access to at the moment can't run cargo miri because of this issue 😢

[pandaman64]

I got another Stacked Borrows violation with GreenNodeBuilder::finish_node.
Minimal reproduction:

use rowan::{GreenNodeBuilder, SyntaxKind};

fn main() {
    let mut builder = GreenNodeBuilder::new();
    builder.start_node(SyntaxKind(0));
    builder.token(SyntaxKind(1), "foo");
    builder.finish_node(); // added this line
}

In this case, the UB occurs inside <HeaderSlice<H, [T; 0]> as Deref>::deref, which seems to be very relevant to the concern raised in CAD97's comment.
As far as I understand, self: &HeaderSlice<H, [T; 0]> gives us SharedReadOnly only for the header part, and we are forging a reference for the entire slice from it.

backtrace

$ MIRIFLAGS='-Zmiri-track-raw-pointers' cargo +nightly miri run
    Finished dev [unoptimized + debuginfo] target(s) in 0.01s
     Running `/home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/bin/cargo-miri target/miri/x86_64-unknown-linux-gnu/debug/rowan-miri`
error: Undefined Behavior: trying to reborrow for SharedReadOnly at alloc1879+0x18, but parent tag <6966> does not have an appropriate item in the borrow stack
   --> /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/arc.rs:264:13
    |
264 |             &*(fake_slice as *const HeaderSlice<H, [T]>)
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ trying to reborrow for SharedReadOnly at alloc1879+0x18, but parent tag <6966> does not have an appropriate item in the borrow stack
    |
    = 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
            
    = note: inside `<rowan::arc::HeaderSlice<rowan::green::token::GreenTokenHead, [u8; 0]> as std::ops::Deref>::deref` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/arc.rs:264:13
    = note: inside `rowan::GreenTokenData::text` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/token.rs:101:48
    = note: inside `rowan::GreenTokenData::text_len` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/token.rs:107:22
    = note: inside `rowan::green::element::<impl rowan::NodeOrToken<&rowan::GreenNodeData, &rowan::GreenTokenData>>::text_len` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/element.rs:86:39
    = note: inside `rowan::green::element::<impl rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>>::text_len` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/element.rs:67:9
    = note: inside closure at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/node.rs:216:25
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<(rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>,)> for &mut [closure@rowan::GreenNode::new<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>>::{closure#0}]>::call_once` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:280:13
    = note: inside `std::option::Option::<rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>>::map::<rowan::green::node::GreenChild, &mut [closure@rowan::GreenNode::new<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>>::{closure#0}]>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/option.rs:823:29
    = note: inside `<std::iter::Map<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>, [closure@rowan::GreenNode::new<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>>::{closure#0}]> as std::iter::Iterator>::next` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/iter/adapters/map.rs:101:9
    = note: inside `rowan::arc::ThinArc::<rowan::green::node::GreenNodeHead, rowan::green::node::GreenChild>::from_header_and_iter::<std::iter::Map<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>, [closure@rowan::GreenNode::new<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>>::{closure#0}]>>` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/arc.rs:384:25
    = note: inside `rowan::GreenNode::new::<std::iter::Map<std::vec::Drain<(u64, rowan::NodeOrToken<rowan::GreenNode, rowan::GreenToken>)>, [closure@rowan::green::builder::NodeCache::node::{closure#0}::{closure#0}]>>` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/node.rs:223:20
    = note: inside closure at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/builder.rs:28:13
    = note: inside `rowan::green::builder::NodeCache::node` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/builder.rs:69:28
    = note: inside `rowan::GreenNodeBuilder::finish_node` at /home/pan/.cargo/registry/src/github.com-1ecc6299db9ec823/rowan-0.13.0-pre.8/src/green/builder.rs:149:28
note: inside `main` at src/main.rs:7:5
   --> src/main.rs:7:5
    |
7   |     builder.finish_node();
    |     ^^^^^^^^^^^^^^^^^^^^^
    = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
    = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:125:18
    = note: inside closure at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:63:18
    = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
    = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside closure at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:48
    = note: inside `std::panicking::r#try::do_call::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:401:40
    = note: inside `std::panicking::r#try::<isize, [closure@std::rt::lang_start_internal::{closure#2}]>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:365:19
    = note: inside `std::panic::catch_unwind::<[closure@std::rt::lang_start_internal::{closure#2}], isize>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:434:14
    = note: inside `std::rt::lang_start_internal` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:45:20
    = note: inside `std::rt::lang_start::<()>` at /home/pan/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:62:5

error: aborting due to previous error

[CAD97]

Yikes, this reliance on &Header fattening goes deeper than I thought. General temperature is that we would like to allow this pattern (and likely might need to in order to support extern type), as it's been independently rewritten multiple times and is something people expect to work.

There are two approaches I see towards getting rowan to work under miri again:

• drop all use of smart pointers or references to header types (this includes e.g. GreenNodeData) and use raw pointers instead (and/or custom handles wrapping raw pointers), or
• put some more effort into exploring and adopting sorbus's approach, using my pointer utilities to make correct thin pointers easier.