From 218caa410aa38c29984be31a5229b9fa717560ee Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:19:13 +0200 Subject: Merging upstream version 1.68.2+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/src/vec/drain.rs | 6 ++--- library/alloc/src/vec/into_iter.rs | 52 ++++++++++++++++++++++++++++++-------- library/alloc/src/vec/is_zero.rs | 22 ++++++++++++++-- library/alloc/src/vec/mod.rs | 15 +++++++---- library/alloc/src/vec/splice.rs | 6 +++++ 5 files changed, 80 insertions(+), 21 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs index 541f99bcf..2b1a787cc 100644 --- a/library/alloc/src/vec/drain.rs +++ b/library/alloc/src/vec/drain.rs @@ -223,9 +223,9 @@ impl Drop for Drain<'_, T, A> { } // as_slice() must only be called when iter.len() is > 0 because - // vec::Splice modifies vec::Drain fields and may grow the vec which would invalidate - // the iterator's internal pointers. Creating a reference to deallocated memory - // is invalid even when it is zero-length + // it also gets touched by vec::Splice which may turn it into a dangling pointer + // which would make it and the vec pointer point to different allocations which would + // lead to invalid pointer arithmetic below. let drop_ptr = iter.as_slice().as_ptr(); unsafe { diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 02cc7691a..37966007e 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -1,6 +1,8 @@ #[cfg(not(no_global_oom_handling))] use super::AsVecIntoIter; use crate::alloc::{Allocator, Global}; +#[cfg(not(no_global_oom_handling))] +use crate::collections::VecDeque; use crate::raw_vec::RawVec; use core::array; use core::fmt; @@ -38,7 +40,9 @@ pub struct IntoIter< // to avoid dropping the allocator twice we need to wrap it into ManuallyDrop pub(super) alloc: ManuallyDrop, pub(super) ptr: *const T, - pub(super) end: *const T, + pub(super) end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that + // ptr == end is a quick test for the Iterator being empty, that works + // for both ZST and non-ZST. } #[stable(feature = "vec_intoiter_debug", since = "1.13.0")] @@ -130,7 +134,36 @@ impl IntoIter { /// Forgets to Drop the remaining elements while still allowing the backing allocation to be freed. pub(crate) fn forget_remaining_elements(&mut self) { - self.ptr = self.end; + // For th ZST case, it is crucial that we mutate `end` here, not `ptr`. + // `ptr` must stay aligned, while `end` may be unaligned. + self.end = self.ptr; + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + pub(crate) fn into_vecdeque(self) -> VecDeque { + // Keep our `Drop` impl from dropping the elements and the allocator + let mut this = ManuallyDrop::new(self); + + // SAFETY: This allocation originally came from a `Vec`, so it passes + // all those checks. We have `this.buf` ≤ `this.ptr` ≤ `this.end`, + // so the `sub_ptr`s below cannot wrap, and will produce a well-formed + // range. `end` ≤ `buf + cap`, so the range will be in-bounds. + // Taking `alloc` is ok because nothing else is going to look at it, + // since our `Drop` impl isn't going to run so there's no more code. + unsafe { + let buf = this.buf.as_ptr(); + let initialized = if T::IS_ZST { + // All the pointers are the same for ZSTs, so it's fine to + // say that they're all at the beginning of the "allocation". + 0..this.len() + } else { + this.ptr.sub_ptr(buf)..this.end.sub_ptr(buf) + }; + let cap = this.cap; + let alloc = ManuallyDrop::take(&mut this.alloc); + VecDeque::from_contiguous_raw_parts_in(buf, initialized, cap, alloc) + } } } @@ -155,10 +188,9 @@ impl Iterator for IntoIter { if self.ptr == self.end { None } else if T::IS_ZST { - // purposefully don't use 'ptr.offset' because for - // vectors with 0-size elements this would return the - // same pointer. - self.ptr = self.ptr.wrapping_byte_add(1); + // `ptr` has to stay where it is to remain aligned, so we reduce the length by 1 by + // reducing the `end`. + self.end = self.end.wrapping_byte_sub(1); // Make up a value of this ZST. Some(unsafe { mem::zeroed() }) @@ -185,10 +217,8 @@ impl Iterator for IntoIter { let step_size = self.len().min(n); let to_drop = ptr::slice_from_raw_parts_mut(self.ptr as *mut T, step_size); if T::IS_ZST { - // SAFETY: due to unchecked casts of unsigned amounts to signed offsets the wraparound - // effectively results in unsigned pointers representing positions 0..usize::MAX, - // which is valid for ZSTs. - self.ptr = self.ptr.wrapping_byte_add(step_size); + // See `next` for why we sub `end` here. + self.end = self.end.wrapping_byte_sub(step_size); } else { // SAFETY: the min() above ensures that step_size is in bounds self.ptr = unsafe { self.ptr.add(step_size) }; @@ -221,7 +251,7 @@ impl Iterator for IntoIter { return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) }); } - self.ptr = self.ptr.wrapping_byte_add(N); + self.end = self.end.wrapping_byte_sub(N); // Safety: ditto return Ok(unsafe { raw_ary.transpose().assume_init() }); } diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs index 8e652d676..cb9adf05c 100644 --- a/library/alloc/src/vec/is_zero.rs +++ b/library/alloc/src/vec/is_zero.rs @@ -4,7 +4,8 @@ use crate::boxed::Box; #[rustc_specialization_trait] pub(super) unsafe trait IsZero { - /// Whether this value's representation is all zeros + /// Whether this value's representation is all zeros, + /// or can be represented with all zeroes. fn is_zero(&self) -> bool; } @@ -57,7 +58,7 @@ unsafe impl IsZero for [T; N] { #[inline] fn is_zero(&self) -> bool { // Because this is generated as a runtime check, it's not obvious that - // it's worth doing if the array is really long. The threshold here + // it's worth doing if the array is really long. The threshold here // is largely arbitrary, but was picked because as of 2022-07-01 LLVM // fails to const-fold the check in `vec![[1; 32]; n]` // See https://github.com/rust-lang/rust/pull/97581#issuecomment-1166628022 @@ -147,6 +148,23 @@ impl_is_zero_option_of_nonzero!( NonZeroIsize, ); +macro_rules! impl_is_zero_option_of_num { + ($($t:ty,)+) => {$( + unsafe impl IsZero for Option<$t> { + #[inline] + fn is_zero(&self) -> bool { + const { + let none: Self = unsafe { core::mem::MaybeUninit::zeroed().assume_init() }; + assert!(none.is_none()); + } + self.is_none() + } + } + )+}; +} + +impl_is_zero_option_of_num!(u8, u16, u32, u64, u128, i8, i16, i32, i64, i128, usize, isize,); + unsafe impl IsZero for Wrapping { #[inline] fn is_zero(&self) -> bool { diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index ba34ab680..36b0b3c9e 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -166,7 +166,7 @@ mod spec_extend; /// vec[0] = 7; /// assert_eq!(vec[0], 7); /// -/// vec.extend([1, 2, 3].iter().copied()); +/// vec.extend([1, 2, 3]); /// /// for x in &vec { /// println!("{x}"); @@ -490,6 +490,8 @@ impl Vec { /// This is highly unsafe, due to the number of invariants that aren't /// checked: /// + /// * `ptr` must have been allocated using the global allocator, such as via + /// the [`alloc::alloc`] function. /// * `T` needs to have the same alignment as what `ptr` was allocated with. /// (`T` having a less strict alignment is not sufficient, the alignment really /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be @@ -526,6 +528,7 @@ impl Vec { /// function. /// /// [`String`]: crate::string::String + /// [`alloc::alloc`]: crate::alloc::alloc /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc /// /// # Examples @@ -681,6 +684,7 @@ impl Vec { /// This is highly unsafe, due to the number of invariants that aren't /// checked: /// + /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`. /// * `T` needs to have the same alignment as what `ptr` was allocated with. /// (`T` having a less strict alignment is not sufficient, the alignment really /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be @@ -714,6 +718,7 @@ impl Vec { /// /// [`String`]: crate::string::String /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc + /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory /// [*fit*]: crate::alloc::Allocator#memory-fitting /// /// # Examples @@ -2424,7 +2429,7 @@ impl Vec { self.reserve(range.len()); // SAFETY: - // - `slice::range` guarantees that the given range is valid for indexing self + // - `slice::range` guarantees that the given range is valid for indexing self unsafe { self.spec_extend_from_within(range); } @@ -2681,7 +2686,7 @@ impl Clone for Vec { // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is // required for this method definition, is not available. Instead use the - // `slice::to_vec` function which is only available with cfg(test) + // `slice::to_vec` function which is only available with cfg(test) // NB see the slice::hack module in slice.rs for more information #[cfg(test)] fn clone(&self) -> Self { @@ -3191,7 +3196,7 @@ where } } -// note: test pulls in libstd, which causes errors here +// note: test pulls in std, which causes errors here #[cfg(not(test))] #[stable(feature = "vec_from_box", since = "1.18.0")] impl From> for Vec { @@ -3209,7 +3214,7 @@ impl From> for Vec { } } -// note: test pulls in libstd, which causes errors here +// note: test pulls in std, which causes errors here #[cfg(not(no_global_oom_handling))] #[cfg(not(test))] #[stable(feature = "box_from_vec", since = "1.20.0")] diff --git a/library/alloc/src/vec/splice.rs b/library/alloc/src/vec/splice.rs index bad765c7f..1861147fe 100644 --- a/library/alloc/src/vec/splice.rs +++ b/library/alloc/src/vec/splice.rs @@ -54,6 +54,12 @@ impl ExactSizeIterator for Splice<'_, I, A> {} impl Drop for Splice<'_, I, A> { fn drop(&mut self) { self.drain.by_ref().for_each(drop); + // At this point draining is done and the only remaining tasks are splicing + // and moving things into the final place. + // Which means we can replace the slice::Iter with pointers that won't point to deallocated + // memory, so that Drain::drop is still allowed to call iter.len(), otherwise it would break + // the ptr.sub_ptr contract. + self.drain.iter = (&[]).iter(); unsafe { if self.drain.tail_len == 0 { -- cgit v1.2.3