From 9918693037dce8aa4bb6f08741b6812923486c18 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 19 Jun 2024 11:26:03 +0200 Subject: Merging upstream version 1.76.0+dfsg1. Signed-off-by: Daniel Baumann --- library/alloc/src/vec/in_place_collect.rs | 164 +++++++++++++++++++++++++----- library/alloc/src/vec/in_place_drop.rs | 26 +++-- library/alloc/src/vec/into_iter.rs | 16 ++- library/alloc/src/vec/mod.rs | 66 +++++++++--- library/alloc/src/vec/spec_from_elem.rs | 23 ++++- library/alloc/src/vec/spec_from_iter.rs | 14 +-- 6 files changed, 243 insertions(+), 66 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 5ecd04799..e68cce04c 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -6,11 +6,11 @@ //! The specialization in this module applies to iterators in the shape of //! `source.adapter().adapter().adapter().collect::>()` //! where `source` is an owning iterator obtained from [`Vec`], [`Box<[T]>`][box] (by conversion to `Vec`) -//! or [`BinaryHeap`], the adapters each consume one or more items per step -//! (represented by [`InPlaceIterable`]), provide transitive access to `source` (via [`SourceIter`]) -//! and thus the underlying allocation. And finally the layouts of `T` and `U` must -//! have the same size and alignment, this is currently ensured via const eval instead of trait bounds -//! in the specialized [`SpecFromIter`] implementation. +//! or [`BinaryHeap`], the adapters guarantee to consume enough items per step to make room +//! for the results (represented by [`InPlaceIterable`]), provide transitive access to `source` +//! (via [`SourceIter`]) and thus the underlying allocation. +//! And finally there are alignment and size constriants to consider, this is currently ensured via +//! const eval instead of trait bounds in the specialized [`SpecFromIter`] implementation. //! //! [`BinaryHeap`]: crate::collections::BinaryHeap //! [box]: crate::boxed::Box @@ -35,11 +35,28 @@ //! the step of reading a value and getting a reference to write to. Instead raw pointers must be //! used on the reader and writer side. //! -//! That writes never clobber a yet-to-be-read item is ensured by the [`InPlaceIterable`] requirements. +//! That writes never clobber a yet-to-be-read items is ensured by the [`InPlaceIterable`] requirements. //! //! # Layout constraints //! -//! [`Allocator`] requires that `allocate()` and `deallocate()` have matching alignment and size. +//! When recycling an allocation between different types we must uphold the [`Allocator`] contract +//! which means that the input and output Layouts have to "fit". +//! +//! To complicate things further `InPlaceIterable` supports splitting or merging items into smaller/ +//! larger ones to enable (de)aggregation of arrays. +//! +//! Ultimately each step of the iterator must free up enough *bytes* in the source to make room +//! for the next output item. +//! If `T` and `U` have the same size no fixup is needed. +//! If `T`'s size is a multiple of `U`'s we can compensate by multiplying the capacity accordingly. +//! Otherwise the input capacity (and thus layout) in bytes may not be representable by the output +//! `Vec`. In that case `alloc.shrink()` is used to update the allocation's layout. +//! +//! Alignments of `T` must be the same or larger than `U`. Since alignments are always a power +//! of two _larger_ implies _is a multiple of_. +//! +//! See `in_place_collectible()` for the current conditions. +//! //! Additionally this specialization doesn't make sense for ZSTs as there is no reallocation to //! avoid and it would make pointer arithmetic more difficult. //! @@ -55,7 +72,7 @@ //! This is handled by the [`InPlaceDrop`] guard for sink items (`U`) and by //! [`vec::IntoIter::forget_allocation_drop_remaining()`] for remaining source items (`T`). //! -//! If dropping any remaining source item (`T`) panics then [`InPlaceDstBufDrop`] will handle dropping +//! If dropping any remaining source item (`T`) panics then [`InPlaceDstDataSrcBufDrop`] will handle dropping //! the already collected sink items (`U`) and freeing the allocation. //! //! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining() @@ -137,44 +154,98 @@ //! } //! vec.truncate(write_idx); //! ``` +use crate::alloc::{handle_alloc_error, Global}; +use core::alloc::Allocator; +use core::alloc::Layout; use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}; +use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, SizedTypeProperties}; -use core::ptr::{self}; +use core::num::NonZeroUsize; +use core::ptr::{self, NonNull}; + +use super::{InPlaceDrop, InPlaceDstDataSrcBufDrop, SpecFromIter, SpecFromIterNested, Vec}; + +const fn in_place_collectible( + step_merge: Option, + step_expand: Option, +) -> bool { + // Require matching alignments because an alignment-changing realloc is inefficient on many + // system allocators and better implementations would require the unstable Allocator trait. + if const { SRC::IS_ZST || DEST::IS_ZST || mem::align_of::() != mem::align_of::() } { + return false; + } -use super::{InPlaceDrop, InPlaceDstBufDrop, SpecFromIter, SpecFromIterNested, Vec}; + match (step_merge, step_expand) { + (Some(step_merge), Some(step_expand)) => { + // At least N merged source items -> at most M expanded destination items + // e.g. + // - 1 x [u8; 4] -> 4x u8, via flatten + // - 4 x u8 -> 1x [u8; 4], via array_chunks + mem::size_of::() * step_merge.get() >= mem::size_of::() * step_expand.get() + } + // Fall back to other from_iter impls if an overflow occurred in the step merge/expansion + // tracking. + _ => false, + } +} + +const fn needs_realloc(src_cap: usize, dst_cap: usize) -> bool { + if const { mem::align_of::() != mem::align_of::() } { + // FIXME: use unreachable! once that works in const + panic!("in_place_collectible() prevents this"); + } -/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the -/// source allocation, i.e. executing the pipeline in place. -#[rustc_unsafe_specialization_marker] -pub(super) trait InPlaceIterableMarker {} + // If src type size is an integer multiple of the destination type size then + // the caller will have calculated a `dst_cap` that is an integer multiple of + // `src_cap` without remainder. + if const { + let src_sz = mem::size_of::(); + let dest_sz = mem::size_of::(); + dest_sz != 0 && src_sz % dest_sz == 0 + } { + return false; + } -impl InPlaceIterableMarker for T where T: InPlaceIterable {} + // type layouts don't guarantee a fit, so do a runtime check to see if + // the allocations happen to match + return src_cap > 0 && src_cap * mem::size_of::() != dst_cap * mem::size_of::(); +} + +/// This provides a shorthand for the source type since local type aliases aren't a thing. +#[rustc_specialization_trait] +trait InPlaceCollect: SourceIter + InPlaceIterable { + type Src; +} + +impl InPlaceCollect for T +where + T: SourceIter + InPlaceIterable, +{ + type Src = <::Source as AsVecIntoIter>::Item; +} impl SpecFromIter for Vec where - I: Iterator + SourceIter + InPlaceIterableMarker, + I: Iterator + InPlaceCollect, + ::Source: AsVecIntoIter, { default fn from_iter(mut iterator: I) -> Self { // See "Layout constraints" section in the module documentation. We rely on const // optimization here since these conditions currently cannot be expressed as trait bounds - if T::IS_ZST - || mem::size_of::() - != mem::size_of::<<::Source as AsVecIntoIter>::Item>() - || mem::align_of::() - != mem::align_of::<<::Source as AsVecIntoIter>::Item>() - { + if const { !in_place_collectible::(I::MERGE_BY, I::EXPAND_BY) } { // fallback to more generic implementations return SpecFromIterNested::from_iter(iterator); } - let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { + let (src_buf, src_ptr, src_cap, mut dst_buf, dst_end, dst_cap) = unsafe { let inner = iterator.as_inner().as_into_iter(); ( inner.buf.as_ptr(), inner.ptr, + inner.cap, inner.buf.as_ptr() as *mut T, inner.end as *const T, - inner.cap, + inner.cap * mem::size_of::() / mem::size_of::(), ) }; @@ -195,19 +266,56 @@ where ); } - // The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`. - // This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation + // The ownership of the source allocation and the new `T` values is temporarily moved into `dst_guard`. + // This is safe because + // * `forget_allocation_drop_remaining` immediately forgets the allocation // before any panic can occur in order to avoid any double free, and then proceeds to drop // any remaining values at the tail of the source. + // * the shrink either panics without invalidating the allocation, aborts or + // succeeds. In the last case we disarm the guard. // // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the // module documentation why this is ok anyway. - let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap }; + let dst_guard = + InPlaceDstDataSrcBufDrop { ptr: dst_buf, len, src_cap, src: PhantomData:: }; src.forget_allocation_drop_remaining(); + + // Adjust the allocation if the source had a capacity in bytes that wasn't a multiple + // of the destination type size. + // Since the discrepancy should generally be small this should only result in some + // bookkeeping updates and no memmove. + if needs_realloc::(src_cap, dst_cap) { + let alloc = Global; + debug_assert_ne!(src_cap, 0); + debug_assert_ne!(dst_cap, 0); + unsafe { + // The old allocation exists, therefore it must have a valid layout. + let src_align = mem::align_of::(); + let src_size = mem::size_of::().unchecked_mul(src_cap); + let old_layout = Layout::from_size_align_unchecked(src_size, src_align); + + // The allocation must be equal or smaller for in-place iteration to be possible + // therefore the new layout must be ≤ the old one and therefore valid. + let dst_align = mem::align_of::(); + let dst_size = mem::size_of::().unchecked_mul(dst_cap); + let new_layout = Layout::from_size_align_unchecked(dst_size, dst_align); + + let result = alloc.shrink( + NonNull::new_unchecked(dst_buf as *mut u8), + old_layout, + new_layout, + ); + let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; + dst_buf = reallocated.as_ptr() as *mut T; + } + } else { + debug_assert_eq!(src_cap * mem::size_of::(), dst_cap * mem::size_of::()); + } + mem::forget(dst_guard); - let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; + let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; vec } diff --git a/library/alloc/src/vec/in_place_drop.rs b/library/alloc/src/vec/in_place_drop.rs index 25ca33c6a..40a540b57 100644 --- a/library/alloc/src/vec/in_place_drop.rs +++ b/library/alloc/src/vec/in_place_drop.rs @@ -1,6 +1,10 @@ -use core::ptr::{self}; +use core::marker::PhantomData; +use core::ptr::{self, drop_in_place}; use core::slice::{self}; +use crate::alloc::Global; +use crate::raw_vec::RawVec; + // A helper struct for in-place iteration that drops the destination slice of iteration, // i.e. the head. The source slice (the tail) is dropped by IntoIter. pub(super) struct InPlaceDrop { @@ -23,17 +27,23 @@ impl Drop for InPlaceDrop { } } -// A helper struct for in-place collection that drops the destination allocation and elements, -// to avoid leaking them if some other destructor panics. -pub(super) struct InPlaceDstBufDrop { - pub(super) ptr: *mut T, +// A helper struct for in-place collection that drops the destination items together with +// the source allocation - i.e. before the reallocation happened - to avoid leaking them +// if some other destructor panics. +pub(super) struct InPlaceDstDataSrcBufDrop { + pub(super) ptr: *mut Dest, pub(super) len: usize, - pub(super) cap: usize, + pub(super) src_cap: usize, + pub(super) src: PhantomData, } -impl Drop for InPlaceDstBufDrop { +impl Drop for InPlaceDstDataSrcBufDrop { #[inline] fn drop(&mut self) { - unsafe { super::Vec::from_raw_parts(self.ptr, self.len, self.cap) }; + unsafe { + let _drop_allocation = + RawVec::::from_raw_parts_in(self.ptr.cast::(), self.src_cap, Global); + drop_in_place(core::ptr::slice_from_raw_parts_mut::(self.ptr, self.len)); + }; } } diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index b2db2fdfd..b03e04b7c 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -7,7 +7,8 @@ use crate::raw_vec::RawVec; use core::array; use core::fmt; use core::iter::{ - FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce, + FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen, + TrustedRandomAccessNoCoerce, }; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; @@ -285,9 +286,7 @@ impl Iterator for IntoIter { // Also note the implementation of `Self: TrustedRandomAccess` requires // that `T: Copy` so reading elements from the buffer doesn't invalidate // them for `Drop`. - unsafe { - if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } - } + unsafe { if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } } } } @@ -339,6 +338,10 @@ impl ExactSizeIterator for IntoIter { #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for IntoIter {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl TrustedFused for IntoIter {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl TrustedLen for IntoIter {} @@ -423,7 +426,10 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter { // also refer to the vec::in_place_collect module documentation to get an overview #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl InPlaceIterable for IntoIter {} +unsafe impl InPlaceIterable for IntoIter { + const EXPAND_BY: Option = NonZeroUsize::new(1); + const MERGE_BY: Option = NonZeroUsize::new(1); +} #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 6c78d65f1..b2e920397 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -58,6 +58,7 @@ use core::cmp; use core::cmp::Ordering; use core::fmt; use core::hash::{Hash, Hasher}; +#[cfg(not(no_global_oom_handling))] use core::iter; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; @@ -101,6 +102,7 @@ mod into_iter; #[cfg(not(no_global_oom_handling))] use self::is_zero::IsZero; +#[cfg(not(no_global_oom_handling))] mod is_zero; #[cfg(not(no_global_oom_handling))] @@ -121,7 +123,7 @@ use self::set_len_on_drop::SetLenOnDrop; mod set_len_on_drop; #[cfg(not(no_global_oom_handling))] -use self::in_place_drop::{InPlaceDrop, InPlaceDstBufDrop}; +use self::in_place_drop::{InPlaceDrop, InPlaceDstDataSrcBufDrop}; #[cfg(not(no_global_oom_handling))] mod in_place_drop; @@ -1775,7 +1777,32 @@ impl Vec { return; } - /* INVARIANT: vec.len() > read >= write > write-1 >= 0 */ + // Check if we ever want to remove anything. + // This allows to use copy_non_overlapping in next cycle. + // And avoids any memory writes if we don't need to remove anything. + let mut first_duplicate_idx: usize = 1; + let start = self.as_mut_ptr(); + while first_duplicate_idx != len { + let found_duplicate = unsafe { + // SAFETY: first_duplicate always in range [1..len) + // Note that we start iteration from 1 so we never overflow. + let prev = start.add(first_duplicate_idx.wrapping_sub(1)); + let current = start.add(first_duplicate_idx); + // We explicitly say in docs that references are reversed. + same_bucket(&mut *current, &mut *prev) + }; + if found_duplicate { + break; + } + first_duplicate_idx += 1; + } + // Don't need to remove anything. + // We cannot get bigger than len. + if first_duplicate_idx == len { + return; + } + + /* INVARIANT: vec.len() > read > write > write-1 >= 0 */ struct FillGapOnDrop<'a, T, A: core::alloc::Allocator> { /* Offset of the element we want to check if it is duplicate */ read: usize, @@ -1821,31 +1848,39 @@ impl Vec { } } - let mut gap = FillGapOnDrop { read: 1, write: 1, vec: self }; - let ptr = gap.vec.as_mut_ptr(); - /* Drop items while going through Vec, it should be more efficient than * doing slice partition_dedup + truncate */ + // Construct gap first and then drop item to avoid memory corruption if `T::drop` panics. + let mut gap = + FillGapOnDrop { read: first_duplicate_idx + 1, write: first_duplicate_idx, vec: self }; + unsafe { + // SAFETY: we checked that first_duplicate_idx in bounds before. + // If drop panics, `gap` would remove this item without drop. + ptr::drop_in_place(start.add(first_duplicate_idx)); + } + /* SAFETY: Because of the invariant, read_ptr, prev_ptr and write_ptr * are always in-bounds and read_ptr never aliases prev_ptr */ unsafe { while gap.read < len { - let read_ptr = ptr.add(gap.read); - let prev_ptr = ptr.add(gap.write.wrapping_sub(1)); + let read_ptr = start.add(gap.read); + let prev_ptr = start.add(gap.write.wrapping_sub(1)); - if same_bucket(&mut *read_ptr, &mut *prev_ptr) { + // We explicitly say in docs that references are reversed. + let found_duplicate = same_bucket(&mut *read_ptr, &mut *prev_ptr); + if found_duplicate { // Increase `gap.read` now since the drop may panic. gap.read += 1; /* We have found duplicate, drop it in-place */ ptr::drop_in_place(read_ptr); } else { - let write_ptr = ptr.add(gap.write); + let write_ptr = start.add(gap.write); - /* Because `read_ptr` can be equal to `write_ptr`, we either - * have to use `copy` or conditional `copy_nonoverlapping`. - * Looks like the first option is faster. */ - ptr::copy(read_ptr, write_ptr, 1); + /* read_ptr cannot be equal to write_ptr because at this point + * we guaranteed to skip at least one element (before loop starts). + */ + ptr::copy_nonoverlapping(read_ptr, write_ptr, 1); /* We have filled that place, so go further */ gap.write += 1; @@ -2599,6 +2634,7 @@ pub fn from_elem_in(elem: T, n: usize, alloc: A) -> Vec< ::from_elem(elem, n, alloc) } +#[cfg(not(no_global_oom_handling))] trait ExtendFromWithinSpec { /// # Safety /// @@ -2607,6 +2643,7 @@ trait ExtendFromWithinSpec { unsafe fn spec_extend_from_within(&mut self, src: Range); } +#[cfg(not(no_global_oom_handling))] impl ExtendFromWithinSpec for Vec { default unsafe fn spec_extend_from_within(&mut self, src: Range) { // SAFETY: @@ -2626,6 +2663,7 @@ impl ExtendFromWithinSpec for Vec { } } +#[cfg(not(no_global_oom_handling))] impl ExtendFromWithinSpec for Vec { unsafe fn spec_extend_from_within(&mut self, src: Range) { let count = src.len(); @@ -2706,7 +2744,7 @@ impl Clone for Vec { /// ``` /// use std::hash::BuildHasher; /// -/// let b = std::collections::hash_map::RandomState::new(); +/// let b = std::hash::RandomState::new(); /// let v: Vec = vec![0xa8, 0x3c, 0x09]; /// let s: &[u8] = &[0xa8, 0x3c, 0x09]; /// assert_eq!(b.hash_one(v), b.hash_one(s)); diff --git a/library/alloc/src/vec/spec_from_elem.rs b/library/alloc/src/vec/spec_from_elem.rs index da43d17bf..01a6db144 100644 --- a/library/alloc/src/vec/spec_from_elem.rs +++ b/library/alloc/src/vec/spec_from_elem.rs @@ -36,12 +36,12 @@ impl SpecFromElem for i8 { if elem == 0 { return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; } + let mut v = Vec::with_capacity_in(n, alloc); unsafe { - let mut v = Vec::with_capacity_in(n, alloc); ptr::write_bytes(v.as_mut_ptr(), elem as u8, n); v.set_len(n); - v } + v } } @@ -51,11 +51,26 @@ impl SpecFromElem for u8 { if elem == 0 { return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; } + let mut v = Vec::with_capacity_in(n, alloc); unsafe { - let mut v = Vec::with_capacity_in(n, alloc); ptr::write_bytes(v.as_mut_ptr(), elem, n); v.set_len(n); - v } + v + } +} + +// A better way would be to implement this for all ZSTs which are `Copy` and have trivial `Clone` +// but the latter cannot be detected currently +impl SpecFromElem for () { + #[inline] + fn from_elem(_elem: (), n: usize, alloc: A) -> Vec<(), A> { + let mut v = Vec::with_capacity_in(n, alloc); + // SAFETY: the capacity has just been set to `n` + // and `()` is a ZST with trivial `Clone` implementation + unsafe { + v.set_len(n); + } + v } } diff --git a/library/alloc/src/vec/spec_from_iter.rs b/library/alloc/src/vec/spec_from_iter.rs index efa686847..2ddfdde59 100644 --- a/library/alloc/src/vec/spec_from_iter.rs +++ b/library/alloc/src/vec/spec_from_iter.rs @@ -13,13 +13,13 @@ use super::{IntoIter, SpecExtend, SpecFromIterNested, Vec}; /// +-+-----------+ /// | /// v -/// +-+-------------------------------+ +---------------------+ -/// |SpecFromIter +---->+SpecFromIterNested | -/// |where I: | | |where I: | -/// | Iterator (default)----------+ | | Iterator (default) | -/// | vec::IntoIter | | | TrustedLen | -/// | SourceIterMarker---fallback-+ | +---------------------+ -/// +---------------------------------+ +/// +-+---------------------------------+ +---------------------+ +/// |SpecFromIter +---->+SpecFromIterNested | +/// |where I: | | |where I: | +/// | Iterator (default)------------+ | | Iterator (default) | +/// | vec::IntoIter | | | TrustedLen | +/// | InPlaceCollect--(fallback to)-+ | +---------------------+ +/// +-----------------------------------+ /// ``` pub(super) trait SpecFromIter { fn from_iter(iter: I) -> Self; -- cgit v1.2.3