Stacked borrows fails on {ChunksMut,ChunksExactMut}::__iterator_get_unchecked()

[andylizi]

Description

fn main() {
    let mut arr1 = [0u8; 64];
    let arr2 = [0u8; 64];
    let mut iter = arr1.chunks_mut(8).zip(arr2.chunks(8));
    while let Some((chunk1, chunk2)) = iter.next() {
        dbg!(chunk2[0]);
        dbg!(chunk1[0]);
        iter.next();
        dbg!(chunk2[0]);
        dbg!(chunk1[0]);  // error here
    }
}

Running this code in Miri will produce the following output:

[src\main.rs:6] chunk2[0] = 0
[src\main.rs:7] chunk1[0] = 0
[src\main.rs:9] chunk2[0] = 0
error: Undefined Behavior: no item granting read access to tag <1832> at alloc906 found in borrow stack.
  --> src\main.rs:10:9
   |
10 |         dbg!(chunk1[0]);  // error here
   |         ^^^^^^^^^^^^^^^ no item granting read access to tag <1832> at alloc906 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

With -Zmiri-track-pointer-tag=1832,1585,12319

note: tracking was triggered
    --> \library\core\src\slice\iter.rs:1564:19
     |
1564 |         Self { v: slice, chunk_size: size }
     |                   ^^^^^ created tag 1585
     |
     = note: inside `std::slice::ChunksMut::<u8>::new` at \library\core\src\slice\iter.rs:1564:19
     = note: inside `core::slice::<impl [u8]>::chunks_mut` at \library\core\src\slice\mod.rs:828:9
note: inside `main` at src\main.rs:4:20
    --> src\main.rs:4:20
     |
4    |     let mut iter = arr1.chunks_mut(8).zip(arr2.chunks(8));
     |                    ^^^^^^^^^^^^^^^^^^

note: tracking was triggered
 --> src\main.rs:5:21
  |
5 |     while let Some((chunk1, chunk2)) = iter.next() {
  |                     ^^^^^^ created tag 1832
  |
  = note: inside `main` at src\main.rs:5:21

[src\main.rs:6] chunk2[0] = 0
[src\main.rs:7] chunk1[0] = 0

note: tracking was triggered
    --> \library\core\src\slice\iter.rs:1641:32
     |
1641 |             let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
     |                                ^^^^^^^^^^^^ popped tracked tag for item [Unique for <1832>] due to Read access for <1585>
     |
     = note: inside `<std::slice::ChunksMut<u8> as std::iter::Iterator>::__iterator_get_unchecked` at \library\core\src\slice\iter.rs:1641:32
     = note: inside `<std::iter::Zip<std::slice::ChunksMut<u8>, std::slice::Chunks<u8>> as std::iter::adapters::zip::ZipImpl<std::slice::ChunksMut<u8>, std::slice::Chunks<u8>>>::next` at \library\core\src\iter\adapters\zip.rs:278:23
     = note: inside `<std::iter::Zip<std::slice::ChunksMut<u8>, std::slice::Chunks<u8>> as std::iter::Iterator>::next` at \library\core\src\iter\adapters\zip.rs:84:9
    --> \library\core\src\slice\iter.rs:1642:32
     |
1642 |             from_raw_parts_mut(self.v.as_mut_ptr().add(start), len)
     |                                ^^^^^^^^^^^^^^^^^^^ created tag 12319
     |
     = note: inside `<std::slice::ChunksMut<u8> as std::iter::Iterator>::__iterator_get_unchecked` at \library\core\src\slice\iter.rs:1642:32
    --> \library\core\src\slice\mod.rs:483:5
      |
  483 | /     pub const fn as_mut_ptr(&mut self) -> *mut T {
  484 | |         self as *mut [T] as *mut T
  485 | |     }
      | |_____^ popped tracked tag for item [Disabled for <1832>] due to Write access for <12319>
      |
      = note: inside `core::slice::<impl [u8]>::as_mut_ptr` at \library\core\src\slice\mod.rs:483:5
      = note: inside `<std::slice::ChunksMut<u8> as std::iter::Iterator>::__iterator_get_unchecked` at \library\core\src\slice\iter.rs:1642:32
     note: inside `main` at src\main.rs:8:9
    --> src\main.rs:8:9
     |
8    |         iter.next();
     |         ^^^^^^^^^^^
     = note

[src\main.rs:9] chunk2[0] = 0

error: Undefined Behavior: no item granting read access to tag <1832> at alloc906 found in borrow stack.
  --> src\main.rs:10:9
   |
10 |         dbg!(chunk1[0]);  // error here
   |         ^^^^^^^^^^^^^^^ no item granting read access to tag <1832> at alloc906 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

A few things to note here:

1. Access to the mutable chunk will fail. For example arr1.chunks(8).zip(arr2.chunks_mut(8)) will fail on chunk2[0] instead.
2. zip() is required. This is probably due to Zip uses __iterator_get_unchecked() internally rather than next().
3. chunks_mut() and chunks_exact_mut() can both reproduce.
4. array_chunks_mut() can't reproduce.

Environment

$ rustc --version --verbose
rustc 1.61.0-nightly (45e2c2881 2022-02-20)
binary: rustc
commit-hash: 45e2c2881d11324d610815bfff097e25c412199e
commit-date: 2022-02-20
host: x86_64-pc-windows-msvc
release: 1.61.0-nightly
LLVM version: 14.0.0

$ cargo miri --version
miri 0.1.0 (0db4090 2022-02-12)

[RalfJung]

There's probably more of these kinds of problems that @saethlin has been looking into recently.

[saethlin]

Huge thanks for reporting this @andylizi!

This is definitely an issue with the implementation in core. Perhaps this issue should be moved to rust-lang/rust? (as in, by someone with permission to move the issue itself, not closed and a new one opened)

The existing definition of ChunksMut:

rust/library/core/src/slice/iter.rs

Lines 1556 to 1559 in 1103d2e

	pub struct ChunksMut<'a, T: 'a> {
	v: &'a mut [T],
	chunk_size: usize,
	}

Cannot support the current implementation of __iterator_get_unchecked:

rust/library/core/src/slice/iter.rs

Lines 1632 to 1644 in 1103d2e

	unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
	let start = idx * self.chunk_size;
	// SAFETY: see comments for `Chunks::__iterator_get_unchecked`.
	//
	// Also note that the caller also guarantees that we're never called
	// with the same index again, and that no other methods that will
	// access this subslice are called, so it is valid for the returned
	// slice to be mutable.
	unsafe {
	let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
	from_raw_parts_mut(self.v.as_mut_ptr().add(start), len)
	}
	}

The problem is that this method is trying to hand out subslices of a &mut [T] while also holding on to the original. Because it wraps a &mut [T], ChunksMut guarantees that its inner slice always shrinks when it returns a slice. It looks like this guarantee was accidentally introduced and accidentally upheld in implementation by avoiding unsafe... until __iterator_get_unchecked was added.

I'm working on a patch that fixes the aliasing problem.

It's perhaps worth noting that the specialization on zip that this exists to support has already earned 4 I-unsound issues, and this aliasing issue isn't due to new code. We/I should have caught this already, but didn't. That's quite annoying.

[RalfJung]

All right, I moved this to the Rust repo.

[the8472]

has already earned 4 I-unsound issues

For large values of 4.
#85873, #85863, #82282, #80670, #82291, #81740, #86443

[scottmcm]

Nominating for libs; it might be worth a conversation about whether this is proving too unreliable to keep doing in the current way.

[the8472]

There's an existing test that covers the combination of ChunksMut and Zip (which exercises get_unchecked) that didn't catch this, so unsafe-code-test-coverage (which was discussed in a recent meeting) wouldn't have helped here.

rust/library/core/tests/slice.rs

Lines 398 to 410 in bd1a869

	#[test]
	fn test_chunks_mut_zip() {
	let v1: &mut [i32] = &mut [0, 1, 2, 3, 4];
	let v2: &[i32] = &[6, 7, 8, 9, 10];
	for (a, b) in v1.chunks_mut(2).zip(v2.chunks(2)) {
	let sum = b.iter().sum::<i32>();
	for v in a {
	*v += sum;
	}
	}
	assert_eq!(v1, [13, 14, 19, 20, 14]);
	}