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.

[m-ou-se]

We assume in lots of places that slice.as_ptr().add(slice.len()) is safe. E.g.

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

Lines 496 to 517 in d408fdd

	pub const fn as_ptr_range(&self) -> Range<*const T> {
	let start = self.as_ptr();
	// SAFETY: The `add` here is safe, because:
	//
	// - Both pointers are part of the same object, as pointing directly
	// past the object also counts.
	//
	// - The size of the slice is never larger than isize::MAX bytes, as
	// noted here:
	// - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447
	// - https://doc.rust-lang.org/reference/behavior-considered-undefined.html
	// - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety
	// (This doesn't seem normative yet, but the very same assumption is
	// made in many places, including the Index implementation of slices.)
	//
	// - There is no wrapping around involved, as slices do not wrap past
	// the end of the address space.
	//
	// See the documentation of pointer::add.
	let end = unsafe { start.add(self.len()) };
	start..end
	}

The documentation for pointer::add does mention that vec.as_ptr().add(vec.len()) is always safe, but doesn't state that clearly for slices in general:

rust/library/core/src/ptr/const_ptr.rs

Lines 195 to 196 in d408fdd

	/// and `Box` ensure they never allocate more than `isize::MAX` bytes, so
	/// `vec.as_ptr().add(vec.len())` is always safe.

The implementation of Index for slices also assumes this is always safe:

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

Lines 166 to 170 in d408fdd

	// SAFETY: the caller guarantees that `slice` is not dangling, so it
	// cannot be longer than `isize::MAX`. They also guarantee that
	// `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
	// so the call to `add` is safe.
	unsafe { slice.as_ptr().add(self) }

[the8472]

Should that part of the allocator API contracts?

[apiraino]

Removing the I-prioritize as it looks like more relevant to documentation
(but in case apply a priority if it helps a follow-up)

@rustbot label -I-prioritize

[RalfJung]

Should that part of the allocator API contracts?

Yes, this effectively already is part of the allocator API contract.