diff options
Diffstat (limited to 'rust/alloc')
-rw-r--r-- | rust/alloc/alloc.rs | 3 | ||||
-rw-r--r-- | rust/alloc/boxed.rs | 14 | ||||
-rw-r--r-- | rust/alloc/collections/mod.rs | 1 | ||||
-rw-r--r-- | rust/alloc/lib.rs | 8 | ||||
-rw-r--r-- | rust/alloc/raw_vec.rs | 58 | ||||
-rw-r--r-- | rust/alloc/vec/into_iter.rs | 16 | ||||
-rw-r--r-- | rust/alloc/vec/mod.rs | 65 |
7 files changed, 123 insertions, 42 deletions
diff --git a/rust/alloc/alloc.rs b/rust/alloc/alloc.rs index 8a6be8c98173..abb791cc2371 100644 --- a/rust/alloc/alloc.rs +++ b/rust/alloc/alloc.rs @@ -425,12 +425,14 @@ pub mod __alloc_error_handler { } } +#[cfg(not(no_global_oom_handling))] /// Specialize clones into pre-allocated, uninitialized memory. /// Used by `Box::clone` and `Rc`/`Arc::make_mut`. pub(crate) trait WriteCloneIntoRaw: Sized { unsafe fn write_clone_into_raw(&self, target: *mut Self); } +#[cfg(not(no_global_oom_handling))] impl<T: Clone> WriteCloneIntoRaw for T { #[inline] default unsafe fn write_clone_into_raw(&self, target: *mut Self) { @@ -440,6 +442,7 @@ impl<T: Clone> WriteCloneIntoRaw for T { } } +#[cfg(not(no_global_oom_handling))] impl<T: Copy> WriteCloneIntoRaw for T { #[inline] unsafe fn write_clone_into_raw(&self, target: *mut Self) { diff --git a/rust/alloc/boxed.rs b/rust/alloc/boxed.rs index f5f40778a193..c93a22a5c97f 100644 --- a/rust/alloc/boxed.rs +++ b/rust/alloc/boxed.rs @@ -1042,10 +1042,18 @@ impl<T: ?Sized, A: Allocator> Box<T, A> { /// use std::ptr; /// /// let x = Box::new(String::from("Hello")); - /// let p = Box::into_raw(x); + /// let ptr = Box::into_raw(x); + /// unsafe { + /// ptr::drop_in_place(ptr); + /// dealloc(ptr as *mut u8, Layout::new::<String>()); + /// } + /// ``` + /// Note: This is equivalent to the following: + /// ``` + /// let x = Box::new(String::from("Hello")); + /// let ptr = Box::into_raw(x); /// unsafe { - /// ptr::drop_in_place(p); - /// dealloc(p as *mut u8, Layout::new::<String>()); + /// drop(Box::from_raw(ptr)); /// } /// ``` /// diff --git a/rust/alloc/collections/mod.rs b/rust/alloc/collections/mod.rs index 2506065d158a..00ffb3b97365 100644 --- a/rust/alloc/collections/mod.rs +++ b/rust/alloc/collections/mod.rs @@ -150,6 +150,7 @@ impl Display for TryReserveError { /// An intermediate trait for specialization of `Extend`. #[doc(hidden)] +#[cfg(not(no_global_oom_handling))] trait SpecExtend<I: IntoIterator> { /// Extends `self` with the contents of the given iterator. fn spec_extend(&mut self, iter: I); diff --git a/rust/alloc/lib.rs b/rust/alloc/lib.rs index 345cf5c9cf92..36f79c075593 100644 --- a/rust/alloc/lib.rs +++ b/rust/alloc/lib.rs @@ -80,8 +80,8 @@ not(no_sync), target_has_atomic = "ptr" ))] -#![cfg_attr(not(bootstrap), doc(rust_logo))] -#![cfg_attr(not(bootstrap), feature(rustdoc_internals))] +#![doc(rust_logo)] +#![feature(rustdoc_internals)] #![no_std] #![needs_allocator] // Lints: @@ -142,7 +142,6 @@ #![feature(maybe_uninit_uninit_array)] #![feature(maybe_uninit_uninit_array_transpose)] #![feature(pattern)] -#![feature(ptr_addr_eq)] #![feature(ptr_internals)] #![feature(ptr_metadata)] #![feature(ptr_sub_ptr)] @@ -157,6 +156,7 @@ #![feature(std_internals)] #![feature(str_internals)] #![feature(strict_provenance)] +#![feature(trusted_fused)] #![feature(trusted_len)] #![feature(trusted_random_access)] #![feature(try_trait_v2)] @@ -277,7 +277,7 @@ pub(crate) mod test_helpers { /// seed not being the same for every RNG invocation too. pub(crate) fn test_rng() -> rand_xorshift::XorShiftRng { use std::hash::{BuildHasher, Hash, Hasher}; - let mut hasher = std::collections::hash_map::RandomState::new().build_hasher(); + let mut hasher = std::hash::RandomState::new().build_hasher(); std::panic::Location::caller().hash(&mut hasher); let hc64 = hasher.finish(); let seed_vec = diff --git a/rust/alloc/raw_vec.rs b/rust/alloc/raw_vec.rs index f1b8cec8cc62..98b6abf30af6 100644 --- a/rust/alloc/raw_vec.rs +++ b/rust/alloc/raw_vec.rs @@ -27,6 +27,16 @@ enum AllocInit { Zeroed, } +#[repr(transparent)] +#[cfg_attr(target_pointer_width = "16", rustc_layout_scalar_valid_range_end(0x7fff))] +#[cfg_attr(target_pointer_width = "32", rustc_layout_scalar_valid_range_end(0x7fff_ffff))] +#[cfg_attr(target_pointer_width = "64", rustc_layout_scalar_valid_range_end(0x7fff_ffff_ffff_ffff))] +struct Cap(usize); + +impl Cap { + const ZERO: Cap = unsafe { Cap(0) }; +} + /// A low-level utility for more ergonomically allocating, reallocating, and deallocating /// a buffer of memory on the heap without having to worry about all the corner cases /// involved. This type is excellent for building your own data structures like Vec and VecDeque. @@ -52,7 +62,12 @@ enum AllocInit { #[allow(missing_debug_implementations)] pub(crate) struct RawVec<T, A: Allocator = Global> { ptr: Unique<T>, - cap: usize, + /// Never used for ZSTs; it's `capacity()`'s responsibility to return usize::MAX in that case. + /// + /// # Safety + /// + /// `cap` must be in the `0..=isize::MAX` range. + cap: Cap, alloc: A, } @@ -121,7 +136,7 @@ impl<T, A: Allocator> RawVec<T, A> { /// the returned `RawVec`. pub const fn new_in(alloc: A) -> Self { // `cap: 0` means "unallocated". zero-sized types are ignored. - Self { ptr: Unique::dangling(), cap: 0, alloc } + Self { ptr: Unique::dangling(), cap: Cap::ZERO, alloc } } /// Like `with_capacity`, but parameterized over the choice of @@ -203,7 +218,7 @@ impl<T, A: Allocator> RawVec<T, A> { // here should change to `ptr.len() / mem::size_of::<T>()`. Self { ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) }, - cap: capacity, + cap: unsafe { Cap(capacity) }, alloc, } } @@ -228,7 +243,7 @@ impl<T, A: Allocator> RawVec<T, A> { // here should change to `ptr.len() / mem::size_of::<T>()`. Ok(Self { ptr: unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) }, - cap: capacity, + cap: unsafe { Cap(capacity) }, alloc, }) } @@ -240,12 +255,13 @@ impl<T, A: Allocator> RawVec<T, A> { /// The `ptr` must be allocated (via the given allocator `alloc`), and with the given /// `capacity`. /// The `capacity` cannot exceed `isize::MAX` for sized types. (only a concern on 32-bit - /// systems). ZST vectors may have a capacity up to `usize::MAX`. + /// systems). For ZSTs capacity is ignored. /// If the `ptr` and `capacity` come from a `RawVec` created via `alloc`, then this is /// guaranteed. #[inline] pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, alloc: A) -> Self { - Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap: capacity, alloc } + let cap = if T::IS_ZST { Cap::ZERO } else { unsafe { Cap(capacity) } }; + Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap, alloc } } /// Gets a raw pointer to the start of the allocation. Note that this is @@ -261,7 +277,7 @@ impl<T, A: Allocator> RawVec<T, A> { /// This will always be `usize::MAX` if `T` is zero-sized. #[inline(always)] pub fn capacity(&self) -> usize { - if T::IS_ZST { usize::MAX } else { self.cap } + if T::IS_ZST { usize::MAX } else { self.cap.0 } } /// Returns a shared reference to the allocator backing this `RawVec`. @@ -270,7 +286,7 @@ impl<T, A: Allocator> RawVec<T, A> { } fn current_memory(&self) -> Option<(NonNull<u8>, Layout)> { - if T::IS_ZST || self.cap == 0 { + if T::IS_ZST || self.cap.0 == 0 { None } else { // We could use Layout::array here which ensures the absence of isize and usize overflows @@ -280,7 +296,7 @@ impl<T, A: Allocator> RawVec<T, A> { let _: () = const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) }; unsafe { let align = mem::align_of::<T>(); - let size = mem::size_of::<T>().unchecked_mul(self.cap); + let size = mem::size_of::<T>().unchecked_mul(self.cap.0); let layout = Layout::from_size_align_unchecked(size, align); Some((self.ptr.cast().into(), layout)) } @@ -414,12 +430,15 @@ impl<T, A: Allocator> RawVec<T, A> { additional > self.capacity().wrapping_sub(len) } - fn set_ptr_and_cap(&mut self, ptr: NonNull<[u8]>, cap: usize) { + /// # Safety: + /// + /// `cap` must not exceed `isize::MAX`. + unsafe fn set_ptr_and_cap(&mut self, ptr: NonNull<[u8]>, cap: usize) { // Allocators currently return a `NonNull<[u8]>` whose length matches // the size requested. If that ever changes, the capacity here should // change to `ptr.len() / mem::size_of::<T>()`. self.ptr = unsafe { Unique::new_unchecked(ptr.cast().as_ptr()) }; - self.cap = cap; + self.cap = unsafe { Cap(cap) }; } // This method is usually instantiated many times. So we want it to be as @@ -444,14 +463,15 @@ impl<T, A: Allocator> RawVec<T, A> { // This guarantees exponential growth. The doubling cannot overflow // because `cap <= isize::MAX` and the type of `cap` is `usize`. - let cap = cmp::max(self.cap * 2, required_cap); + let cap = cmp::max(self.cap.0 * 2, required_cap); let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap); let new_layout = Layout::array::<T>(cap); // `finish_grow` is non-generic over `T`. let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - self.set_ptr_and_cap(ptr, cap); + // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than isize::MAX items + unsafe { self.set_ptr_and_cap(ptr, cap) }; Ok(()) } @@ -470,7 +490,10 @@ impl<T, A: Allocator> RawVec<T, A> { // `finish_grow` is non-generic over `T`. let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - self.set_ptr_and_cap(ptr, cap); + // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than isize::MAX items + unsafe { + self.set_ptr_and_cap(ptr, cap); + } Ok(()) } @@ -488,7 +511,7 @@ impl<T, A: Allocator> RawVec<T, A> { if cap == 0 { unsafe { self.alloc.deallocate(ptr, layout) }; self.ptr = Unique::dangling(); - self.cap = 0; + self.cap = Cap::ZERO; } else { let ptr = unsafe { // `Layout::array` cannot overflow here because it would have @@ -499,7 +522,10 @@ impl<T, A: Allocator> RawVec<T, A> { .shrink(ptr, layout, new_layout) .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })? }; - self.set_ptr_and_cap(ptr, cap); + // SAFETY: if the allocation is valid, then the capacity is too + unsafe { + self.set_ptr_and_cap(ptr, cap); + } } Ok(()) } diff --git a/rust/alloc/vec/into_iter.rs b/rust/alloc/vec/into_iter.rs index aac0ec16aef1..136bfe94af6c 100644 --- a/rust/alloc/vec/into_iter.rs +++ b/rust/alloc/vec/into_iter.rs @@ -9,7 +9,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}; @@ -287,9 +288,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { // 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)) } } } } @@ -341,6 +340,10 @@ impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> { #[stable(feature = "fused", since = "1.26.0")] impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {} +#[doc(hidden)] +#[unstable(issue = "none", feature = "trusted_fused")] +unsafe impl<T, A: Allocator> TrustedFused for IntoIter<T, A> {} + #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {} @@ -425,7 +428,10 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> { // also refer to the vec::in_place_collect module documentation to get an overview #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] -unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {} +unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> { + const EXPAND_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); + const MERGE_BY: Option<NonZeroUsize> = NonZeroUsize::new(1); +} #[unstable(issue = "none", feature = "inplace_iteration")] #[doc(hidden)] diff --git a/rust/alloc/vec/mod.rs b/rust/alloc/vec/mod.rs index 0d95fd7ef337..220fb9d6f45b 100644 --- a/rust/alloc/vec/mod.rs +++ b/rust/alloc/vec/mod.rs @@ -105,6 +105,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))] @@ -123,7 +124,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; @@ -1893,7 +1894,32 @@ impl<T, A: Allocator> Vec<T, A> { 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, @@ -1939,31 +1965,39 @@ impl<T, A: Allocator> Vec<T, A> { } } - 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; @@ -2844,6 +2878,7 @@ pub fn from_elem_in<T: Clone, A: Allocator>(elem: T, n: usize, alloc: A) -> Vec< <T as SpecFromElem>::from_elem(elem, n, alloc) } +#[cfg(not(no_global_oom_handling))] trait ExtendFromWithinSpec { /// # Safety /// @@ -2852,6 +2887,7 @@ trait ExtendFromWithinSpec { unsafe fn spec_extend_from_within(&mut self, src: Range<usize>); } +#[cfg(not(no_global_oom_handling))] impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { default unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) { // SAFETY: @@ -2871,6 +2907,7 @@ impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { } } +#[cfg(not(no_global_oom_handling))] impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { unsafe fn spec_extend_from_within(&mut self, src: Range<usize>) { let count = src.len(); @@ -2951,7 +2988,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> { /// ``` /// use std::hash::BuildHasher; /// -/// let b = std::collections::hash_map::RandomState::new(); +/// let b = std::hash::RandomState::new(); /// let v: Vec<u8> = vec![0xa8, 0x3c, 0x09]; /// let s: &[u8] = &[0xa8, 0x3c, 0x09]; /// assert_eq!(b.hash_one(v), b.hash_one(s)); |