slice::swap violates the aliasing rules

[Darksonn]

The slice::swap method is currently implemented as

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

Lines 544 to 556 in b33e234

	pub fn swap(&mut self, a: usize, b: usize) {
	// Can't take two mutable loans from one vector, so instead just cast
	// them to their raw pointers to do the swap.
	let pa: *mut T = &mut self[a];
	let pb: *mut T = &mut self[b];
	// SAFETY: `pa` and `pb` have been created from safe mutable references and refer
	// to elements in the slice and therefore are guaranteed to be valid and aligned.
	// Note that accessing the elements behind `a` and `b` is checked and will
	// panic when out of bounds.
	unsafe {
	ptr::swap(pa, pb);
	}
	}

If called with a == b, then it first creates a raw pointer to an element in the vector, and then it creates a mutable reference to that same element, asserting exclusive access. It then proceeds to use the original raw pointer even though we just asserted exclusive access through a different reference.

In fact, when running the following program in miri:

fn main() {
    let mut v = vec![1, 2, 3, 4];
    v.swap(2, 2);
}

with MIRIFLAGS="-Zmiri-track-raw-pointers", it fails with an error.

Click to open miri failure

error: Undefined Behavior: no item granting read access to tag <3005> at alloc1335+0x8 found in borrow stack.
    --> /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:1867:14
     |
1867 |     unsafe { copy_nonoverlapping(src, dst, count) }
     |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ no item granting read access to tag <3005> at alloc1335+0x8 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::intrinsics::copy_nonoverlapping::<i32>` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/intrinsics.rs:1867:14
     = note: inside `std::ptr::swap::<i32>` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/ptr/mod.rs:386:9
     = note: inside `core::slice::<impl [i32]>::swap` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/core/src/slice/mod.rs:554:13
note: inside `main` at src/main.rs:3:5
    --> src/main.rs:3:5
     |
3    |     v.swap(2, 2);
     |     ^^^^^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/alice/.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/alice/.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/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:66: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/alice/.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/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:379:40
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panicking.rs:343:19
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/panic.rs:396:14
     = note: inside `std::rt::lang_start_internal` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
     = note: inside `std::rt::lang_start::<()>` at /home/alice/.rustup/toolchains/nightly-x86_64-unknown-linux-gnu/lib/rustlib/src/rust/library/std/src/rt.rs:65:5

Arguably it is also incorrect even when called with a != b since creating the second raw pointer involves first creating a mutable reference to the entire slice, asserting exclusive access to the entire slice. However, miri does not fail in this case.

[SkiFire13]

Arguably it is also incorrect even when called with a != b since creating the second raw pointer involves first creating a mutable reference to the entire slice, asserting exclusive access to the entire slice. However, miri does not fail in this case.

May this have something to do with the fact that slice indexing uses intrinsics?

[oli-obk]

May this have something to do with the fact that slice indexing uses intrinsics?

No, it's because slice indexing uses the IndexMut trait, which returns a mutable reference. So we create two mutable references to the same place, even if we immediately coerce them to a raw pointer. Unfortunately even &raw mut self[a] would not help, because the indexing operaiton itself creates a mutable reference. So I think the only way would be to use [T]::as_mut_ptr() and then offset that pointer. Or potentially use self.as_mut_ptr_range().nth(a).expect("foo"), which feels a bit less fragile.

cc @RalfJung

[SkiFire13]

@oli-obk I'm pretty sure that slice indexing doesn't use IndexMut but intrinsics. In fact IndexMut<usize> is implemented with slice indexing, which would cause infinite recursion if slice indexing didn't use intrinsics.

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

Lines 185 to 189 in 887398f

	#[inline]
	fn index_mut(self, slice: &mut [T]) -> &mut T {
	// N.B., use intrinsic indexing
	&mut (*slice)[self]
	}

Now back at the issue, my point wasn't that the previous borrow isn't invalidated because slice indexing use intrinsics, but that Miri doesn't catch it because it gets confused by the intrinsics.

[oli-obk]

Oh right... well... it's still not intrinsics, it's weird builtin magic, which I know is not really helping the discussion.

Aaaanyway: Your insight was the important one I needed: We can actually fix this by changing the &mut self[a] to &raw mut self[a], no other changes needed. The builtin magic will then never create a mutable reference, but directly create a raw pointer to the destination(s).

[RalfJung]

Good catch!

We can actually fix this by changing the &mut self[a] to &raw mut self[a]

Hm... self is still a reference though, so this still relies on indexing being primitive. But yes, this should work and fix the Miri failure.

Now back at the issue, my point wasn't that the previous borrow isn't invalidated because slice indexing use intrinsics, but that Miri doesn't catch it because it gets confused by the intrinsics.

Well, the idea is that with the primitive operations, no reference to the entire slice is created so the previous borrow is not invalidated -- so Miri is behaving as intended here. But indeed this difference between primitive and non-primitive indexing can be confusing.

[KamilaBorowska]

Could it be rewritten using Cell to avoid the issue?

fn swap<T>(slice: &mut [T], a: usize, b: usize) {
    let slice = Cell::from_mut(slice).as_slice_of_cells();
    slice[a].swap(&slice[b]);
}

[Darksonn]

@xfix Ah, nice, you can do it without unsafe code. I feel like I should have thought of this, considering that I wrote Temporarily opt-in to shared mutation.

[SkiFire13]

Note that Cell<T>::swap has an additional check for when the two &Cells alias, while <[T]>::swap doesn't. While this shouldn't produce an observable behaviour, it is a bit inconsistent and may slightly impact performance

[apiraino]

Assigning P-high as discussed as part of the Prioritization Working Group procedure and removing I-prioritize.

[RalfJung]

Note that Cell<T>::swap has an additional check for when the two &Cells alias, while <[T]>::swap doesn't. While this shouldn't produce an observable behaviour, it is a bit inconsistent and may slightly impact performance

I did not know about Cell::swap (or I had forgotten about it)... this is very interesting, and it makes some rather strong assumption: it assumes that two Cell of the same type will either start at the same address or be disjoint. They may never "partially overlap". That does preclude some other possibly sound APIs...

But anyway, that is just a tangent.

EDIT: oops I should not write such comments when I am sleep-deprived, this makes no sense.^^ Cell::swap calls ptr::swap, not ptr::swap_nonoverlapping, so all is good.

[RalfJung]

Opened #80778.

[RalfJung]

FWIW, in case a != b this can also be viewed as an instance of rust-lang/unsafe-code-guidelines#133. However, for a == b I cannot really see a way that this code could be legal.

[RalfJung]

This PR fixes the problem: #81160