Miri -Zmiri-retag-fields libstd test failure inside VecDeque::drain

[5225225]

Using https://github.com/rust-lang/miri-test-libstd, running MIRIFLAGS="-Zmiri-retag-fields" ./run-test.sh alloc --all-targets collections::vec_deque::tests::test_drain, I get

running 1 test
test collections::vec_deque::tests::test_drain ... error: Undefined Behavior: not granting access to tag <2685105> because incompatible item [SharedReadOnly for <3084900>] is protected by call 841439
    --> /home/jess/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:2547:9
     |
2547 |         copy(src, dst, count)
     |         ^^^^^^^^^^^^^^^^^^^^^ not granting access to tag <2685105> because incompatible item [SharedReadOnly for <3084900>] is protected by call 841439
     |
     = 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: <2685105> was created by a retag at offsets [0x0..0x40]
    --> alloc_miri_test/../liballoc/src/raw_vec.rs:185:45
     |
185  |                 AllocInit::Uninitialized => alloc.allocate(layout),
     |                                             ^^^^^^^^^^^^^^^^^^^^^^
help: <2685105> was protected due to <3084896> which was created here
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:2991:65
     |
2991 |         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
     |                                                                 ^^^^^^^^^^^^^^^^
help: this protector is live for this call
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/spec_extend.rs:17:5
     |
17   | /     default fn spec_extend(&mut self, mut iter: I) {
18   | |         // This function should be the moral equivalent of:
19   | |         //
20   | |         //      for item in iter {
...    |
34   | |         }
35   | |     }
     | |_____^
     = note: backtrace:
     = note: inside `core::intrinsics::copy::<usize>` at /home/jess/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:2547:9
note: inside `collections::vec_deque::VecDeque::<usize>::copy` at alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:273:13
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:273:13
     |
273  |             ptr::copy(self.ptr().add(src), self.ptr().add(dst), len);
     |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `collections::vec_deque::VecDeque::<usize>::wrap_copy` at alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:339:21
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:339:21
     |
339  |                     self.copy(dst, src, len);
     |                     ^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<<collections::vec_deque::drain::Drain<'_, T, A> as core::ops::Drop>::drop::DropGuard<usize, std::alloc::Global> as core::ops::Drop>::drop` at alloc_miri_test/../liballoc/src/collections/vec_deque/drain.rs:95:29
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/drain.rs:95:29
     |
95   | ...                   source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
     |                       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     = note: inside `core::ptr::drop_in_place::<<collections::vec_deque::drain::Drain<'_, T, A> as core::ops::Drop>::drop::DropGuard<usize, std::alloc::Global>> - shim(Some(<collections::vec_deque::drain::Drain<'_, T, A> as core::ops::Drop>::drop::DropGuard<usize, std::alloc::Global>))` at /home/jess/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:487:1
note: inside `<collections::vec_deque::drain::Drain<usize> as core::ops::Drop>::drop` at alloc_miri_test/../liballoc/src/collections/vec_deque/drain.rs:111:24
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/drain.rs:111:24
     |
111  |         DropGuard(self);
     |                        ^
     = note: inside `core::ptr::drop_in_place::<collections::vec_deque::drain::Drain<usize>> - shim(Some(collections::vec_deque::drain::Drain<usize>))` at /home/jess/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:487:1
note: inside `<collections::vec_deque::VecDeque<usize> as collections::vec_deque::spec_extend::SpecExtend<usize, collections::vec_deque::drain::Drain<usize>>>::spec_extend` at alloc_miri_test/../liballoc/src/collections/vec_deque/spec_extend.rs:35:5
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/spec_extend.rs:35:5
     |
35   |     }
     |     ^
note: inside `<collections::vec_deque::VecDeque<usize> as core::iter::Extend<usize>>::extend::<collections::vec_deque::drain::Drain<usize>>` at alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:2991:9
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:2991:9
     |
2991 |         <Self as SpecExtend<T, I::IntoIter>>::spec_extend(self, iter.into_iter());
     |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside `<collections::vec_deque::VecDeque<usize> as core::iter::FromIterator<usize>>::from_iter::<collections::vec_deque::drain::Drain<usize>>` at alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:2951:9
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/mod.rs:2951:9
     |
2951 |         deq.extend(iterator);
     |         ^^^^^^^^^^^^^^^^^^^^
     = note: inside `<collections::vec_deque::drain::Drain<usize> as core::iter::Iterator>::collect::<collections::vec_deque::VecDeque<usize>>` at /home/jess/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/iter/traits/iterator.rs:1836:9
note: inside `collections::vec_deque::tests::test_drain` at alloc_miri_test/../liballoc/src/collections/vec_deque/tests.rs:685:48
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/tests.rs:685:48
     |
685  |                     let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
     |                                                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
note: inside closure at alloc_miri_test/../liballoc/src/collections/vec_deque/tests.rs:670:1
    --> alloc_miri_test/../liballoc/src/collections/vec_deque/tests.rs:670:1
     |
669  |   #[test]
     |   ------- in this procedural macro expansion
670  | / fn test_drain() {
671  | |     let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
672  | |
673  | |     let cap = tester.capacity();
...    |
701  | |     }
702  | | }
     | |_^
     = 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

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

The test is a bit large, will try and shrink this down, but figured I'd make the issue now. I can reproduce this by copy pasting the test into a normal rust file.

[5225225]

use std::collections::VecDeque;

fn main() {
    let mut tester: VecDeque<usize> = VecDeque::with_capacity(3);

    for i in 0..3 {
        tester.push_back(i);
    }

    let _: VecDeque<_> = tester.drain(1..2).collect();
}

And here's a minimal example.

[5225225]

Okay, thinking out loud as to what the problem is.

I'm being told that I can't do this copy, because some allocation that was created, is protected. It's the drop in the spec_extend. When you go to drop tester.drain(1..2), for some reason it can't go and read from it? not granting access to tag <2685105> because incompatible item [SharedReadOnly for <3084900>] is protected by call 841439 implies to me that the Drain has a read pointer.

But okay. spec_extend went and read from the Drain normally. But then, when we go to drop that Drain (inside the spec_extend), that goes and uses the inner pointers mutably. Which is not okay? Have I got this right?

Does that imply that for as long as you're inside the spec_extend, any mutation of the inner buffer is UB, because of the protector?

I looked up stacked borrows and got https://www.ralfj.de/blog/2019/04/30/stacked-borrows-2.html (well, I got the github, which linked to 2.1, but then that doesn't say anything about protectors so I went to this page).

when it says not granting access to tag <2685105> because incompatible item [SharedReadOnly for <3084900>] is protected by call 841439 I have no idea if the "access" it wants is read or write or what. Is that information we have? Can we give like an extra info explaining what the access is? Better yet, generate an error code for this situation, and have a hand written sample of what the problem is, and how to fix it?

---

Apologies for the ramble but I'm both tired and I don't understand stacked borrows and I figured trying to explain the thought process of someone who doesn't understand stacked borrows, trying to debug a stacked borrows issue, would be in some way useful.

[saethlin]

I never gave the protector errors much love because they're relatively rare to encounter. In general, if you're asking "is that information we have" the answer is yes.

I'm wary of writing an error code library with suggestions for Miri because I think the effort there scales relatively poorly. That's why I've focused on surfacing more information in the diagnostics (which as you point out, is notably absent here).

---

Protector errors appear when you attempt to remove or disable a tag which is protected, because it is part of a function argument. Reads disable Unique tags, so this isn't a read. Writes remove ~everything above the granting tag, so since we're removing a SharedReadOnly tag this seems like a write access.

If reborrows and use thereof form a neat stack, you can't run into a protector error. So the problem here is that we're trying to write using a tag which is below the FnEntry retag which occurs due to passing the iterator as an argument. The fix, if it is possible, would involve deriving our write access from the iterator, after the function call in question.

If it interests you, I have a branch which tries to centralize the Stacked Borrows information a bit more and thus make it easier to make richer diagnostics: https://github.com/saethlin/miri/tree/diagnostics-cleanup There's just a lot of other things I want to do so I haven't finished it yet

[saethlin]

We debugged this in the community Discord. The problem is that VecDeque's Drain type:

rust/library/alloc/src/collections/vec_deque/drain.rs

Lines 16 to 25 in 3ae03e0

	pub struct Drain<
	'a,
	T: 'a,
	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
	> {
	after_tail: usize,
	after_head: usize,
	iter: Iter<'a, T>,
	deque: NonNull<VecDeque<T, A>>,
	}

wraps VecDeque's Iter type:

rust/library/alloc/src/collections/vec_deque/iter.rs

Lines 15 to 19 in 3ae03e0

	pub struct Iter<'a, T: 'a> {
	ring: &'a [MaybeUninit<T>],
	tail: usize,
	head: usize,
	}

But this iterator needs to mutate the VecDeque that this Iter borrows. But it can't, because as soon as Drain is passed to a function, field retagging protects the contents of the VecDeque that the inside of Iter borrows.

[CAD97]

That means the fix should fairly simple to use IterMut instead of Iter, right? IterMut is already using a pointer rather than a reference, so Drain aliasing it shouldn't be an issue.

[the8472]

The Drain impls for Vec and VecDeque are a bit bizarre because they keep both the Iter and a NonNull< Vec{Deque}>. In Vec this was solved with this dance:

rust/library/alloc/src/vec/drain.rs

Lines 160 to 169 in 2f320a2

	unsafe {
	// drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
	// a pointer with mutable provenance is necessary. Therefore we must reconstruct
	// it from the original vec but also avoid creating a &mut to the front since that could
	// invalidate raw pointers to it which some unsafe code might rely on.
	let vec_ptr = vec.as_mut().as_mut_ptr();
	let drop_offset = drop_ptr.sub_ptr(vec_ptr);
	let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
	ptr::drop_in_place(to_drop);
	}

but VecDeque wasn't updated to match. Well, that and the respective Iter impl uses references for VecDeque and pointers for Vec.

[5225225]

That means the fix should fairly simple to use IterMut instead of Iter, right? IterMut is already using a pointer rather than a reference, so Drain aliasing it shouldn't be an issue.

yes but also Drain needs to be covariant, and just putting an IterMut in it would make it invariant.

So I'm thinking an internal IterRaw that yields *mut T (and is covariant itself) and does all the logic, with the Iter/IterMut/IntoIter/Drain being thin wrappers over that, might work.

[RalfJung]

Is this a duplicate of #60076?

[5225225]

Looks to be, yes. I'll close this and copy paste my smaller reproduction to that issue