Miri UB in Arc::inner using Arc::clone

[domenicquirl]

I'm using triomphe for the cstree library, a fork of @matklad's rowan syntax tree library used in rust-analyzer. With the latest nightly, miri emits an error for potential undefined behaviour for the reborrow in Arc::inner.

The reborrow occurs while Arc::cloneing a pointer obtained from Arc::new. In the specific instance posted below, it is triggered by the sytax::text::tests::test_text_equality, but I've ran it against other tests and the error is very reproducible in any test that builds a syntax tree.

There were a few miri warnings on the cstree side related to the relatively recent strict provenance development, which I addressed, so only the reborrow remains.

Full Backtrace

test syntax::text::tests::test_text_equality ... error: Undefined Behavior: trying to reborrow <232138> for SharedReadWrite permission at alloc98393[0x0], but that tag does not exist in the borrow stack for this location
 --> /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:214:18
    |
214 |         unsafe { &*self.ptr() }
    |                  ^^^^^^^^^^^^
    |                  |
    |                  trying to reborrow <232138> for SharedReadWrite permission at alloc98393[0x0], but that tag does not exist in the borrow stack for this location
    |                  this error occurs as part of a reborrow at alloc98393[0x0..0x8]
    |
  = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows 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: <232138> was created by a retag at offsets [0x8..0x14]
 --> src/green/token.rs:50:19
    |
50  |         let ptr = Arc::into_raw(Arc::new(data));
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  = note: inside `triomphe::Arc::<green::token::GreenTokenData>::inner` at /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:214:18
  = note: inside `<triomphe::Arc<green::token::GreenTokenData> as std::clone::Clone>::clone` at /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:322:24
note: inside `<green::token::GreenToken as std::clone::Clone>::clone` at src/green/token.rs:103:27
 --> src/green/token.rs:103:27
    |
103 |             Arc::into_raw(Arc::clone(&arc))
    |                           ^^^^^^^^^^^^^^^^
note: inside `green::builder::NodeCache::token` at src/green/builder.rs:216:9
 --> src/green/builder.rs:216:9
    |
216 | /         self.tokens
217 | |             .entry(data)
218 | |             .or_insert_with_key(|data| GreenToken::new(*data))
219 | |             .clone()
    | |____________________^
note: inside `green::builder::GreenNodeBuilder::token` at src/green/builder.rs:408:21
 --> src/green/builder.rs:408:21
    |
408 |         let token = self.cache.token(kind, text);
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::build_tree` at src/syntax/text.rs:421:13
 --> src/syntax/text.rs:421:13
    |
421 |             builder.token(SyntaxKind(92), chunk);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality::do_check` at src/syntax/text.rs:431:34
 --> src/syntax/text.rs:431:34
    |
431 |             let (t1, resolver) = build_tree(t1);
    |                                  ^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality::check` at src/syntax/text.rs:442:13
 --> src/syntax/text.rs:442:13
    |
442 |             do_check(t1, t2);
    |             ^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality` at src/syntax/text.rs:446:9
 --> src/syntax/text.rs:446:9
    |
446 |         check(&[""], &[""]);
    |         ^^^^^^^^^^^^^^^^^^^
note: inside closure at src/syntax/text.rs:429:5
 --> src/syntax/text.rs:429:5
    |
428 |       #[test]
    |       ------- in this procedural macro expansion
429 | /     fn test_text_equality() {
430 | |         fn do_check(t1: &[&str], t2: &[&str]) {
431 | |             let (t1, resolver) = build_tree(t1);
432 | |             let t1 = t1.resolve_text(&resolver);
...   |
456 | |         check(&["{", "abc", "}ab"], &["{", "abc", "}", "ab"]);
457 | |     }
    | |_____^

I've also ran miri again with -Zmiri-track-pointer-tag=232138, which curiously (to me, as a definite non-expert on miri) only shows where the tag is created (which is in Arc::into_raw when constructing the cstree::GreenToken::new) and no pop/tag invalidation (note that there is also no diagnostic note about invalidation in the error), so potentially this could also be Miri misfiring?

Tracking Info

test syntax::text::tests::test_text_equality ... note: tracking was triggered
   --> /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:100:18
    |
100 |         unsafe { &((*self.ptr()).data) as *const _ }
    |                  ^^^^^^^^^^^^^^^^^^^^^ created tag 232138
    |
    = note: inside `triomphe::Arc::<green::token::GreenTokenData>::as_ptr` at /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:100:18
    = note: inside `triomphe::Arc::<green::token::GreenTokenData>::into_raw` at /home/dquirl/.cargo/registry/src/github.lhy31512.workers.dev-1ecc6299db9ec823/triomphe-0.1.6/src/arc.rs:90:19
note: inside `green::token::GreenToken::new` at src/green/token.rs:50:19
   --> src/green/token.rs:50:19
    |
50  |         let ptr = Arc::into_raw(Arc::new(data));
    |                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at src/green/builder.rs:218:40
   --> src/green/builder.rs:218:40
    |
218 |             .or_insert_with_key(|data| GreenToken::new(*data))
    |                                        ^^^^^^^^^^^^^^^^^^^^^^
    = note: inside `std::collections::hash_map::Entry::<green::token::GreenTokenData, green::token::GreenToken>::or_insert_with_key::<[closure@src/green/builder.rs:218:33: 218:62]>` at /home/dquirl/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/collections/hash/map.rs:2577:29
note: inside `green::builder::NodeCache::token` at src/green/builder.rs:216:9
   --> src/green/builder.rs:216:9
    |
216 | /         self.tokens
217 | |             .entry(data)
218 | |             .or_insert_with_key(|data| GreenToken::new(*data))
    | |______________________________________________________________^
note: inside `green::builder::GreenNodeBuilder::token` at src/green/builder.rs:408:21
   --> src/green/builder.rs:408:21
    |
408 |         let token = self.cache.token(kind, text);
    |                     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::build_tree` at src/syntax/text.rs:421:13
   --> src/syntax/text.rs:421:13
    |
421 |             builder.token(SyntaxKind(92), chunk);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality::do_check` at src/syntax/text.rs:431:34
   --> src/syntax/text.rs:431:34
    |
431 |             let (t1, resolver) = build_tree(t1);
    |                                  ^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality::check` at src/syntax/text.rs:442:13
   --> src/syntax/text.rs:442:13
    |
442 |             do_check(t1, t2);
    |             ^^^^^^^^^^^^^^^^
note: inside `syntax::text::tests::test_text_equality` at src/syntax/text.rs:446:9
   --> src/syntax/text.rs:446:9
    |
446 |         check(&[""], &[""]);
    |         ^^^^^^^^^^^^^^^^^^^
note: inside closure at src/syntax/text.rs:429:5
   --> src/syntax/text.rs:429:5
    |
428 |       #[test]
    |       ------- in this procedural macro expansion
429 | /     fn test_text_equality() {
430 | |         fn do_check(t1: &[&str], t2: &[&str]) {
431 | |             let (t1, resolver) = build_tree(t1);
432 | |             let t1 = t1.resolve_text(&resolver);
...   |
456 | |         check(&["{", "abc", "}ab"], &["{", "abc", "}", "ab"]);
457 | |     }
    | |_____^
    = note: this note originates in the attribute macro `test` (in Nightly builds, run with -Z macro-backtrace for more info)

Nightly version: rustc 1.64.0-nightly (7425fb293 2022-06-30).

Worked with rustc 1.63.0-nightly (76761db59 2022-05-24).

[Manishearth]

Hmmm. triomphe was written before a lot of the niceties for doing pointer stuff existed. I don't have the time to figure this out, but I suspect whatever operation we're doing there is one that can be done safely; we're not doing much different from what std's Arc does.

[Manishearth]

Also, your crate is doing a lot of pointer into/from raw stuff, any chance you can make a minimal example that doesn't involve your crate?

[RalfJung]

I've also ran miri again with -Zmiri-track-pointer-tag=232138, which curiously (to me, as a definite non-expert on miri) only shows where the tag is created (which is in Arc::into_raw when constructing the cstree::GreenToken::new) and no pop/tag invalidation (note that there is also no diagnostic note about invalidation in the error), so potentially this could also be Miri misfiring?

Usually this means that the pointer was used outside the range of memory that the tag is valid for. If the tag is valid for 0x00..0x04, and then a pointer is used at offset 0x08, then the tag never got popped/invalidated, but it is still invalid to use for that offset.

You are not the first to be taken off-guard by this. We should probably include memory ranges in those messages, to make this less confusing.

[domenicquirl]

Thank you both (and also @saethlin) for your kind responses and for being so quick to address this issue.

You are not the first to be taken off-guard by this. We should probably include memory ranges in those messages, to make this less confusing.

@RalfJung I see you already implemented this. As a small addendum, I also opened rust-lang/miri#2316 to clarify the README regarding the tracking flag. I think part of why I was confused is that right now it only mentions tag invalidation as its effect, which contributed to my feeling that somehow output was missing from miri.