Slices that cover the last byte of the address space are invalid

[joboet]

The current implementation uses pointer::add to compute the end pointer for the bounds check:

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

Lines 88 to 102 in 69e1d22

	pub(super) fn new(slice: &'a [T]) -> Self {
	let ptr = slice.as_ptr();
	// SAFETY: Similar to `IterMut::new`.
	unsafe {
	assume(!ptr.is_null());
	let end = if mem::size_of::<T>() == 0 {
	(ptr as *const u8).wrapping_add(slice.len()) as *const T
	} else {
	ptr.add(slice.len())
	};
	Self { ptr: NonNull::new_unchecked(ptr as *mut T), end, _marker: PhantomData }
	}
	}

The method requires that the calculation will not overflow a usize, however that is not always the case. For instance, an allocator might return the last available page (0xfffff000 on x86) and correctly return a slice of u8 (with size 4096 on x86). If a program now iterates over the slice, the end pointer will overflow, wrapping around the address space and thus creating UB.

This behaviour is extremely unlikely and only occurs with no_std as most kernels reserve the higher half of the address space anyway.

Solutions

• Use wrapping_add instead, which avoids the UB, but might disable some optimizations
• Update the requirements for allocators so they aren't allowed to return the last bit of memory
• …

[the8472]

vec::IntoIter is constructed in a similar fashion

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

Lines 2429 to 2439 in 010c236

	fn into_iter(self) -> IntoIter<T, A> {
	unsafe {
	let mut me = ManuallyDrop::new(self);
	let alloc = ptr::read(me.allocator());
	let begin = me.as_mut_ptr();
	let end = if mem::size_of::<T>() == 0 {
	arith_offset(begin as *const i8, me.len() as isize) as *const T
	} else {
	begin.add(me.len()) as *const T
	};
	let cap = me.buf.capacity();

array::IntoIter on the other hand uses a different idiom

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

Lines 26 to 33 in 010c236

	data: [MaybeUninit<T>; N],
	/// The elements in `data` that have not been yielded yet.
	///
	/// Invariants:
	/// - `alive.start <= alive.end`
	/// - `alive.end <= N`
	alive: Range<usize>,

[joboet]

@rustbot label A-iterators C-bug

[est31]

@rustbot label I-unsound 💥

[rustbot]

Error: Label 💥 can only be set by Rust team members

Please let @rust-lang/release know if you're having trouble with this bot.

[RalfJung]

The method requires that the calculation will not overflow a usize, however that is not always the case. For instance, an allocator might return the last available page (0xfffff000 on x86) and correctly return a slice of u8 (with size 4096 on x86). If a program now iterates over the slice, the end pointer will overflow, wrapping around the address space and thus creating UB.

An allocator must ensure that the one-past-the-end address of an allocation does not overflow. In other words, 0xffffffff can never be inside an allocation, it can only be one-past-the-end of an allocation. I think this rules out your example, doesn't it?

[joboet]

Yes, that would solve the issue! I can't seem to find it in the documentation, however. Should I change the labeling of this issue to make it a doc-bug?

[RalfJung]

Yeah this could certainly be documented better.

[scottmcm]

I think this has always been part of the implicit invariant for slices, but it would definitely be good to mention it explicitly in things like the documentation for https://doc.rust-lang.org/std/slice/fn.from_raw_parts.html#safety (The last bullet there is coming from the expectation that data.offset(len) needs to be valid, it doesn't seem to be directly mentioned.)

[RalfJung]

This is not really specific to slices though, it is a property of all "allocated objects" in Rust and the allocator must comply by it.