From cb2703945ca3c6c9664a5a9ec606430cb79ba2c8 Mon Sep 17 00:00:00 2001 From: Matthew Jasper Date: Sun, 19 Apr 2020 12:34:00 +0100 Subject: Use min_specialization in liballoc - Remove a type parameter from `[A]RcFromIter`. - Remove an implementation of `[A]RcFromIter` that didn't actually specialize anything. - Remove unused implementation of `IsZero` for `Option<&mut T>`. - Change specializations of `[A]RcEqIdent` to use a marker trait version of `Eq`. - Remove `BTreeClone`. I couldn't find a way to make this work with `min_specialization`. - Add `rustc_unsafe_specialization_marker` to `Copy` and `TrustedLen`. --- src/liballoc/collections/btree/map.rs | 53 ----------------------------------- src/liballoc/lib.rs | 2 +- src/liballoc/rc.rs | 46 +++++++++++++----------------- src/liballoc/sync.rs | 40 +++++++++----------------- src/liballoc/vec.rs | 21 ++++++-------- 5 files changed, 42 insertions(+), 120 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/collections/btree/map.rs b/src/liballoc/collections/btree/map.rs index 099687bd6b0..61d2295ba8c 100644 --- a/src/liballoc/collections/btree/map.rs +++ b/src/liballoc/collections/btree/map.rs @@ -215,59 +215,6 @@ impl Clone for BTreeMap { clone_subtree(self.root.as_ref().unwrap().as_ref()) } } - - fn clone_from(&mut self, other: &Self) { - BTreeClone::clone_from(self, other); - } -} - -trait BTreeClone { - fn clone_from(&mut self, other: &Self); -} - -impl BTreeClone for BTreeMap { - default fn clone_from(&mut self, other: &Self) { - *self = other.clone(); - } -} - -impl BTreeClone for BTreeMap { - fn clone_from(&mut self, other: &Self) { - // This truncates `self` to `other.len()` by calling `split_off` on - // the first key after `other.len()` elements if it exists. - let split_off_key = if self.len() > other.len() { - let diff = self.len() - other.len(); - if diff <= other.len() { - self.iter().nth_back(diff - 1).map(|pair| (*pair.0).clone()) - } else { - self.iter().nth(other.len()).map(|pair| (*pair.0).clone()) - } - } else { - None - }; - if let Some(key) = split_off_key { - self.split_off(&key); - } - - let mut siter = self.range_mut(..); - let mut oiter = other.iter(); - // After truncation, `self` is at most as long as `other` so this loop - // replaces every key-value pair in `self`. Since `oiter` is in sorted - // order and the structure of the `BTreeMap` stays the same, - // the BTree invariants are maintained at the end of the loop. - while !siter.is_empty() { - if let Some((ok, ov)) = oiter.next() { - // SAFETY: This is safe because `siter` is nonempty. - let (sk, sv) = unsafe { siter.next_unchecked() }; - sk.clone_from(ok); - sv.clone_from(ov); - } else { - break; - } - } - // If `other` is longer than `self`, the remaining elements are inserted. - self.extend(oiter.map(|(k, v)| ((*k).clone(), (*v).clone()))); - } } impl super::Recover for BTreeMap diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs index ecec1fb039b..3ebb5662350 100644 --- a/src/liballoc/lib.rs +++ b/src/liballoc/lib.rs @@ -108,7 +108,7 @@ #![feature(ptr_offset_from)] #![feature(rustc_attrs)] #![feature(receiver_trait)] -#![feature(specialization)] +#![feature(min_specialization)] #![feature(staged_api)] #![feature(std_internals)] #![feature(str_internals)] diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs index 2f9505ec79f..307f6714f32 100644 --- a/src/liballoc/rc.rs +++ b/src/liballoc/rc.rs @@ -249,7 +249,7 @@ use core::mem::{self, align_of, align_of_val, forget, size_of_val}; use core::ops::{CoerceUnsized, Deref, DispatchFromDyn, Receiver}; use core::pin::Pin; use core::ptr::{self, NonNull}; -use core::slice::{self, from_raw_parts_mut}; +use core::slice::from_raw_parts_mut; use crate::alloc::{box_free, handle_alloc_error, AllocInit, AllocRef, Global, Layout}; use crate::string::String; @@ -1221,6 +1221,12 @@ impl RcEqIdent for Rc { } } +// Hack to allow specializing on `Eq` even though `Eq` has a method. +#[rustc_unsafe_specialization_marker] +pub(crate) trait MarkerEq: PartialEq {} + +impl MarkerEq for T {} + /// We're doing this specialization here, and not as a more general optimization on `&T`, because it /// would otherwise add a cost to all equality checks on refs. We assume that `Rc`s are used to /// store large values, that are slow to clone, but also heavy to check for equality, causing this @@ -1229,7 +1235,7 @@ impl RcEqIdent for Rc { /// /// We can only do this when `T: Eq` as a `PartialEq` might be deliberately irreflexive. #[stable(feature = "rust1", since = "1.0.0")] -impl RcEqIdent for Rc { +impl RcEqIdent for Rc { #[inline] fn eq(&self, other: &Rc) -> bool { Rc::ptr_eq(self, other) || **self == **other @@ -1548,25 +1554,25 @@ impl iter::FromIterator for Rc<[T]> { /// # assert_eq!(&*evens, &*(0..10).collect::>()); /// ``` fn from_iter>(iter: I) -> Self { - RcFromIter::from_iter(iter.into_iter()) + ToRcSlice::to_rc_slice(iter.into_iter()) } } /// Specialization trait used for collecting into `Rc<[T]>`. -trait RcFromIter { - fn from_iter(iter: I) -> Self; +trait ToRcSlice: Iterator + Sized { + fn to_rc_slice(self) -> Rc<[T]>; } -impl> RcFromIter for Rc<[T]> { - default fn from_iter(iter: I) -> Self { - iter.collect::>().into() +impl> ToRcSlice for I { + default fn to_rc_slice(self) -> Rc<[T]> { + self.collect::>().into() } } -impl> RcFromIter for Rc<[T]> { - default fn from_iter(iter: I) -> Self { +impl> ToRcSlice for I { + fn to_rc_slice(self) -> Rc<[T]> { // This is the case for a `TrustedLen` iterator. - let (low, high) = iter.size_hint(); + let (low, high) = self.size_hint(); if let Some(high) = high { debug_assert_eq!( low, @@ -1577,29 +1583,15 @@ impl> RcFromIter for Rc<[T]> { unsafe { // SAFETY: We need to ensure that the iterator has an exact length and we have. - Rc::from_iter_exact(iter, low) + Rc::from_iter_exact(self, low) } } else { // Fall back to normal implementation. - iter.collect::>().into() + self.collect::>().into() } } } -impl<'a, T: 'a + Clone> RcFromIter<&'a T, slice::Iter<'a, T>> for Rc<[T]> { - fn from_iter(iter: slice::Iter<'a, T>) -> Self { - // Delegate to `impl From<&[T]> for Rc<[T]>`. - // - // In the case that `T: Copy`, we get to use `ptr::copy_nonoverlapping` - // which is even more performant. - // - // In the fall-back case we have `T: Clone`. This is still better - // than the `TrustedLen` implementation as slices have a known length - // and so we get to avoid calling `size_hint` and avoid the branching. - iter.as_slice().into() - } -} - /// `Weak` is a version of [`Rc`] that holds a non-owning reference to the /// managed allocation. The allocation is accessed by calling [`upgrade`] on the `Weak` /// pointer, which returns an [`Option`]`<`[`Rc`]`>`. diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs index a81e0cf7e1d..2b71378619c 100644 --- a/src/liballoc/sync.rs +++ b/src/liballoc/sync.rs @@ -20,7 +20,7 @@ use core::mem::{self, align_of, align_of_val, size_of_val}; use core::ops::{CoerceUnsized, Deref, DispatchFromDyn, Receiver}; use core::pin::Pin; use core::ptr::{self, NonNull}; -use core::slice::{self, from_raw_parts_mut}; +use core::slice::from_raw_parts_mut; use core::sync::atomic; use core::sync::atomic::Ordering::{Acquire, Relaxed, Release, SeqCst}; @@ -1779,7 +1779,7 @@ impl ArcEqIdent for Arc { /// /// We can only do this when `T: Eq` as a `PartialEq` might be deliberately irreflexive. #[stable(feature = "rust1", since = "1.0.0")] -impl ArcEqIdent for Arc { +impl ArcEqIdent for Arc { #[inline] fn eq(&self, other: &Arc) -> bool { Arc::ptr_eq(self, other) || **self == **other @@ -2105,25 +2105,25 @@ impl iter::FromIterator for Arc<[T]> { /// # assert_eq!(&*evens, &*(0..10).collect::>()); /// ``` fn from_iter>(iter: I) -> Self { - ArcFromIter::from_iter(iter.into_iter()) + ToArcSlice::to_arc_slice(iter.into_iter()) } } /// Specialization trait used for collecting into `Arc<[T]>`. -trait ArcFromIter { - fn from_iter(iter: I) -> Self; +trait ToArcSlice: Iterator + Sized { + fn to_arc_slice(self) -> Arc<[T]>; } -impl> ArcFromIter for Arc<[T]> { - default fn from_iter(iter: I) -> Self { - iter.collect::>().into() +impl> ToArcSlice for I { + default fn to_arc_slice(self) -> Arc<[T]> { + self.collect::>().into() } } -impl> ArcFromIter for Arc<[T]> { - default fn from_iter(iter: I) -> Self { +impl> ToArcSlice for I { + fn to_arc_slice(self) -> Arc<[T]> { // This is the case for a `TrustedLen` iterator. - let (low, high) = iter.size_hint(); + let (low, high) = self.size_hint(); if let Some(high) = high { debug_assert_eq!( low, @@ -2134,29 +2134,15 @@ impl> ArcFromIter for Arc<[T]> { unsafe { // SAFETY: We need to ensure that the iterator has an exact length and we have. - Arc::from_iter_exact(iter, low) + Arc::from_iter_exact(self, low) } } else { // Fall back to normal implementation. - iter.collect::>().into() + self.collect::>().into() } } } -impl<'a, T: 'a + Clone> ArcFromIter<&'a T, slice::Iter<'a, T>> for Arc<[T]> { - fn from_iter(iter: slice::Iter<'a, T>) -> Self { - // Delegate to `impl From<&[T]> for Arc<[T]>`. - // - // In the case that `T: Copy`, we get to use `ptr::copy_nonoverlapping` - // which is even more performant. - // - // In the fall-back case we have `T: Clone`. This is still better - // than the `TrustedLen` implementation as slices have a known length - // and so we get to avoid calling `size_hint` and avoid the branching. - iter.as_slice().into() - } -} - #[stable(feature = "rust1", since = "1.0.0")] impl borrow::Borrow for Arc { fn borrow(&self) -> &T { diff --git a/src/liballoc/vec.rs b/src/liballoc/vec.rs index b4a9da84787..624ca2820d7 100644 --- a/src/liballoc/vec.rs +++ b/src/liballoc/vec.rs @@ -1619,8 +1619,8 @@ impl Vec { #[unstable(feature = "vec_resize_default", issue = "41758")] #[rustc_deprecated( reason = "This is moving towards being removed in favor \ - of `.resize_with(Default::default)`. If you disagree, please comment \ - in the tracking issue.", + of `.resize_with(Default::default)`. If you disagree, please comment \ + in the tracking issue.", since = "1.33.0" )] pub fn resize_default(&mut self, new_len: usize) { @@ -1825,6 +1825,7 @@ impl SpecFromElem for T { } } +#[rustc_specialization_trait] unsafe trait IsZero { /// Whether this value is zero fn is_zero(&self) -> bool; @@ -1874,9 +1875,12 @@ unsafe impl IsZero for *mut T { } } -// `Option<&T>`, `Option<&mut T>` and `Option>` are guaranteed to represent `None` as null. -// For fat pointers, the bytes that would be the pointer metadata in the `Some` variant -// are padding in the `None` variant, so ignoring them and zero-initializing instead is ok. +// `Option<&T>` and `Option>` are guaranteed to represent `None` as null. +// For fat pointers, the bytes that would be the pointer metadata in the `Some` +// variant are padding in the `None` variant, so ignoring them and +// zero-initializing instead is ok. +// `Option<&mut T>` never implements `Clone`, so there's no need for an impl of +// `SpecFromElem`. unsafe impl IsZero for Option<&T> { #[inline] @@ -1885,13 +1889,6 @@ unsafe impl IsZero for Option<&T> { } } -unsafe impl IsZero for Option<&mut T> { - #[inline] - fn is_zero(&self) -> bool { - self.is_none() - } -} - unsafe impl IsZero for Option> { #[inline] fn is_zero(&self) -> bool { -- cgit 1.4.1-3-g733a5 From c66d02e3ba0d5ace4e42bab88e4df246f03b91d5 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Fri, 1 May 2020 11:16:38 +0200 Subject: liballoc tests: Miri supports threads now --- src/liballoc/alloc/tests.rs | 2 +- src/liballoc/collections/linked_list/tests.rs | 1 - src/liballoc/collections/vec_deque/tests.rs | 8 ++++---- src/liballoc/sync/tests.rs | 2 -- 4 files changed, 5 insertions(+), 8 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/alloc/tests.rs b/src/liballoc/alloc/tests.rs index 1ad40eca93b..1c003983df9 100644 --- a/src/liballoc/alloc/tests.rs +++ b/src/liballoc/alloc/tests.rs @@ -23,7 +23,7 @@ fn allocate_zeroed() { } #[bench] -#[cfg_attr(miri, ignore)] // Miri does not support benchmarks +#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn alloc_owned_small(b: &mut Bencher) { b.iter(|| { let _: Box<_> = box 10; diff --git a/src/liballoc/collections/linked_list/tests.rs b/src/liballoc/collections/linked_list/tests.rs index 085f734ed91..b8c93a28bba 100644 --- a/src/liballoc/collections/linked_list/tests.rs +++ b/src/liballoc/collections/linked_list/tests.rs @@ -182,7 +182,6 @@ fn test_insert_prev() { #[test] #[cfg_attr(target_os = "emscripten", ignore)] -#[cfg_attr(miri, ignore)] // Miri does not support threads fn test_send() { let n = list_from(&[1, 2, 3]); thread::spawn(move || { diff --git a/src/liballoc/collections/vec_deque/tests.rs b/src/liballoc/collections/vec_deque/tests.rs index 0a3f3300323..fc2ec7908e8 100644 --- a/src/liballoc/collections/vec_deque/tests.rs +++ b/src/liballoc/collections/vec_deque/tests.rs @@ -3,7 +3,7 @@ use super::*; use test; #[bench] -#[cfg_attr(miri, ignore)] // Miri does not support benchmarks +#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_push_back_100(b: &mut test::Bencher) { let mut deq = VecDeque::with_capacity(101); b.iter(|| { @@ -16,7 +16,7 @@ fn bench_push_back_100(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // Miri does not support benchmarks +#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_push_front_100(b: &mut test::Bencher) { let mut deq = VecDeque::with_capacity(101); b.iter(|| { @@ -29,7 +29,7 @@ fn bench_push_front_100(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // Miri does not support benchmarks +#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_pop_back_100(b: &mut test::Bencher) { let mut deq = VecDeque::::with_capacity(101); @@ -43,7 +43,7 @@ fn bench_pop_back_100(b: &mut test::Bencher) { } #[bench] -#[cfg_attr(miri, ignore)] // Miri does not support benchmarks +#[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks fn bench_pop_front_100(b: &mut test::Bencher) { let mut deq = VecDeque::::with_capacity(101); diff --git a/src/liballoc/sync/tests.rs b/src/liballoc/sync/tests.rs index edc2820ee22..4a5cc9aa591 100644 --- a/src/liballoc/sync/tests.rs +++ b/src/liballoc/sync/tests.rs @@ -32,7 +32,6 @@ impl Drop for Canary { #[test] #[cfg_attr(target_os = "emscripten", ignore)] -#[cfg_attr(miri, ignore)] // Miri does not support threads fn manually_share_arc() { let v = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; let arc_v = Arc::new(v); @@ -337,7 +336,6 @@ fn test_ptr_eq() { #[test] #[cfg_attr(target_os = "emscripten", ignore)] -#[cfg_attr(miri, ignore)] // Miri does not support threads fn test_weak_count_locked() { let mut a = Arc::new(atomic::AtomicBool::new(false)); let a2 = a.clone(); -- cgit 1.4.1-3-g733a5 From 7bea58eeac3a5a5280810623f06eadb3a8b891a3 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Sun, 3 May 2020 12:34:53 +0200 Subject: fix test_weak_count_locked for Miri --- src/liballoc/sync/tests.rs | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'src/liballoc') diff --git a/src/liballoc/sync/tests.rs b/src/liballoc/sync/tests.rs index 4a5cc9aa591..a2bb651e2b7 100644 --- a/src/liballoc/sync/tests.rs +++ b/src/liballoc/sync/tests.rs @@ -340,7 +340,9 @@ fn test_weak_count_locked() { let mut a = Arc::new(atomic::AtomicBool::new(false)); let a2 = a.clone(); let t = thread::spawn(move || { - for _i in 0..1000000 { + // Miri is too slow + let count = if cfg!(miri) { 1000 } else { 1000000 }; + for _i in 0..count { Arc::get_mut(&mut a); } a.store(true, SeqCst); @@ -349,6 +351,8 @@ fn test_weak_count_locked() { while !a2.load(SeqCst) { let n = Arc::weak_count(&a2); assert!(n < 2, "bad weak count: {}", n); + #[cfg(miri)] // Miri's scheduler does not guarantee liveness, and thus needs this hint. + atomic::spin_loop_hint(); } t.join().unwrap(); } -- cgit 1.4.1-3-g733a5 From a3cc435f5755f5550d4235779de58b53a22f0f1e Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 11 May 2020 11:46:13 +1000 Subject: Remove `RawVec::double_in_place`. It's unused. --- src/liballoc/raw_vec.rs | 18 ------------------ 1 file changed, 18 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs index a8e19c9cbaa..ac5399acddb 100644 --- a/src/liballoc/raw_vec.rs +++ b/src/liballoc/raw_vec.rs @@ -269,24 +269,6 @@ impl RawVec { } } - /// Attempts to double the size of the type's backing allocation in place. This is common - /// enough to want to do that it's easiest to just have a dedicated method. Slightly - /// more efficient logic can be provided for this than the general case. - /// - /// Returns `true` if the reallocation attempt has succeeded. - /// - /// # Panics - /// - /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust - /// all `usize::MAX` slots in your imaginary buffer. - /// * Panics on 32-bit platforms if the requested capacity exceeds - /// `isize::MAX` bytes. - #[inline(never)] - #[cold] - pub fn double_in_place(&mut self) -> bool { - self.grow(Double, InPlace, Uninitialized).is_ok() - } - /// Ensures that the buffer contains at least enough space to hold /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have /// enough capacity, will reallocate enough space plus comfortable slack -- cgit 1.4.1-3-g733a5 From f420726566587862ef4da9153fbc2800ed444033 Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 11 May 2020 12:26:59 +1000 Subject: Remove `RawVec::double`. It's only used once, for `VecDeque`, and can easily be replaced by something else. The commit changes `grow_if_necessary` to `grow` to avoid some small regressions caused by changed inlining. The commit also removes `Strategy::Double`, and streamlines the remaining variants of `Strategy`. It's a compile time win on some benchmarks because the many instantations of `RawVec::grow` are a little smaller. --- src/liballoc/collections/vec_deque.rs | 20 +++++--- src/liballoc/raw_vec.rs | 91 ++++------------------------------- 2 files changed, 23 insertions(+), 88 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/collections/vec_deque.rs b/src/liballoc/collections/vec_deque.rs index 2f50234b6d5..540649c61b3 100644 --- a/src/liballoc/collections/vec_deque.rs +++ b/src/liballoc/collections/vec_deque.rs @@ -1354,7 +1354,9 @@ impl VecDeque { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn push_front(&mut self, value: T) { - self.grow_if_necessary(); + if self.is_full() { + self.grow(); + } self.tail = self.wrap_sub(self.tail, 1); let tail = self.tail; @@ -1377,7 +1379,9 @@ impl VecDeque { /// ``` #[stable(feature = "rust1", since = "1.0.0")] pub fn push_back(&mut self, value: T) { - self.grow_if_necessary(); + if self.is_full() { + self.grow(); + } let head = self.head; self.head = self.wrap_add(self.head, 1); @@ -1485,7 +1489,9 @@ impl VecDeque { #[stable(feature = "deque_extras_15", since = "1.5.0")] pub fn insert(&mut self, index: usize, value: T) { assert!(index <= self.len(), "index out of bounds"); - self.grow_if_necessary(); + if self.is_full() { + self.grow(); + } // Move the least number of elements in the ring buffer and insert // the given object @@ -2003,11 +2009,13 @@ impl VecDeque { } // This may panic or abort - #[inline] - fn grow_if_necessary(&mut self) { + #[inline(never)] + fn grow(&mut self) { if self.is_full() { let old_cap = self.cap(); - self.buf.double(); + // Double the buffer size. + self.buf.reserve_exact(old_cap, old_cap); + assert!(self.cap() == old_cap * 2); unsafe { self.handle_capacity_increase(old_cap); } diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs index ac5399acddb..921ef447be0 100644 --- a/src/liballoc/raw_vec.rs +++ b/src/liballoc/raw_vec.rs @@ -211,64 +211,6 @@ impl RawVec { } } - /// Doubles the size of the type's backing allocation. This is common enough - /// to want to do that it's easiest to just have a dedicated method. Slightly - /// more efficient logic can be provided for this than the general case. - /// - /// This function is ideal for when pushing elements one-at-a-time because - /// you don't need to incur the costs of the more general computations - /// reserve needs to do to guard against overflow. You do however need to - /// manually check if your `len == capacity`. - /// - /// # Panics - /// - /// * Panics if `T` is zero-sized on the assumption that you managed to exhaust - /// all `usize::MAX` slots in your imaginary buffer. - /// * Panics on 32-bit platforms if the requested capacity exceeds - /// `isize::MAX` bytes. - /// - /// # Aborts - /// - /// Aborts on OOM - /// - /// # Examples - /// - /// ``` - /// # #![feature(raw_vec_internals)] - /// # extern crate alloc; - /// # use std::ptr; - /// # use alloc::raw_vec::RawVec; - /// struct MyVec { - /// buf: RawVec, - /// len: usize, - /// } - /// - /// impl MyVec { - /// pub fn push(&mut self, elem: T) { - /// if self.len == self.buf.capacity() { self.buf.double(); } - /// // double would have aborted or panicked if the len exceeded - /// // `isize::MAX` so this is safe to do unchecked now. - /// unsafe { - /// ptr::write(self.buf.ptr().add(self.len), elem); - /// } - /// self.len += 1; - /// } - /// } - /// # fn main() { - /// # let mut vec = MyVec { buf: RawVec::new(), len: 0 }; - /// # vec.push(1); - /// # } - /// ``` - #[inline(never)] - #[cold] - pub fn double(&mut self) { - match self.grow(Double, MayMove, Uninitialized) { - Err(CapacityOverflow) => capacity_overflow(), - Err(AllocError { layout, .. }) => handle_alloc_error(layout), - Ok(()) => { /* yay */ } - } - } - /// Ensures that the buffer contains at least enough space to hold /// `used_capacity + needed_extra_capacity` elements. If it doesn't already have /// enough capacity, will reallocate enough space plus comfortable slack @@ -336,7 +278,7 @@ impl RawVec { needed_extra_capacity: usize, ) -> Result<(), TryReserveError> { if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Amortized { used_capacity, needed_extra_capacity }, MayMove, Uninitialized) + self.grow(Amortized, used_capacity, needed_extra_capacity, MayMove, Uninitialized) } else { Ok(()) } @@ -363,7 +305,7 @@ impl RawVec { // This is more readable than putting this in one line: // `!self.needs_to_grow(...) || self.grow(...).is_ok()` if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Amortized { used_capacity, needed_extra_capacity }, InPlace, Uninitialized) + self.grow(Amortized, used_capacity, needed_extra_capacity, InPlace, Uninitialized) .is_ok() } else { true @@ -405,7 +347,7 @@ impl RawVec { needed_extra_capacity: usize, ) -> Result<(), TryReserveError> { if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Exact { used_capacity, needed_extra_capacity }, MayMove, Uninitialized) + self.grow(Exact, used_capacity, needed_extra_capacity, MayMove, Uninitialized) } else { Ok(()) } @@ -432,9 +374,8 @@ impl RawVec { #[derive(Copy, Clone)] enum Strategy { - Double, - Amortized { used_capacity: usize, needed_extra_capacity: usize }, - Exact { used_capacity: usize, needed_extra_capacity: usize }, + Amortized, + Exact, } use Strategy::*; @@ -459,6 +400,8 @@ impl RawVec { fn grow( &mut self, strategy: Strategy, + used_capacity: usize, + needed_extra_capacity: usize, placement: ReallocPlacement, init: AllocInit, ) -> Result<(), TryReserveError> { @@ -469,23 +412,7 @@ impl RawVec { return Err(CapacityOverflow); } let new_layout = match strategy { - Double => unsafe { - // Since we guarantee that we never allocate more than `isize::MAX` bytes, - // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow. - // Additionally the alignment will never be too large as to "not be satisfiable", - // so `Layout::from_size_align` will always return `Some`. - // - // TL;DR, we bypass runtime checks due to dynamic assertions in this module, - // allowing us to use `from_size_align_unchecked`. - let cap = if self.cap == 0 { - // Skip to 4 because tiny `Vec`'s are dumb; but not if that would cause overflow. - if elem_size > usize::MAX / 8 { 1 } else { 4 } - } else { - self.cap * 2 - }; - Layout::from_size_align_unchecked(cap * elem_size, mem::align_of::()) - }, - Amortized { used_capacity, needed_extra_capacity } => { + Amortized => { // Nothing we can really do about these checks, sadly. let required_cap = used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; @@ -495,7 +422,7 @@ impl RawVec { let cap = cmp::max(double_cap, required_cap); Layout::array::(cap).map_err(|_| CapacityOverflow)? } - Exact { used_capacity, needed_extra_capacity } => { + Exact => { let cap = used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; Layout::array::(cap).map_err(|_| CapacityOverflow)? -- cgit 1.4.1-3-g733a5 From 68b75033ad78d88872450a81745cacfc11e58178 Mon Sep 17 00:00:00 2001 From: Nicholas Nethercote Date: Mon, 11 May 2020 13:17:28 +1000 Subject: Split `RawVec::grow` up. The amortized case is much more common than the exact case, and it is typically instantiated many times. Also, we can put a chunk of the code into a function that isn't generic over T, which reduces the amount of LLVM IR generated quite a lot, improving compile times. --- src/liballoc/raw_vec.rs | 129 +++++++++++++++++++++++++++++------------------- 1 file changed, 79 insertions(+), 50 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/raw_vec.rs b/src/liballoc/raw_vec.rs index 921ef447be0..d46bf81f996 100644 --- a/src/liballoc/raw_vec.rs +++ b/src/liballoc/raw_vec.rs @@ -1,7 +1,7 @@ #![unstable(feature = "raw_vec_internals", reason = "implementation detail", issue = "none")] #![doc(hidden)] -use core::alloc::MemoryBlock; +use core::alloc::{LayoutErr, MemoryBlock}; use core::cmp; use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::Drop; @@ -278,7 +278,7 @@ impl RawVec { needed_extra_capacity: usize, ) -> Result<(), TryReserveError> { if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Amortized, used_capacity, needed_extra_capacity, MayMove, Uninitialized) + self.grow_amortized(used_capacity, needed_extra_capacity, MayMove) } else { Ok(()) } @@ -305,8 +305,7 @@ impl RawVec { // This is more readable than putting this in one line: // `!self.needs_to_grow(...) || self.grow(...).is_ok()` if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Amortized, used_capacity, needed_extra_capacity, InPlace, Uninitialized) - .is_ok() + self.grow_amortized(used_capacity, needed_extra_capacity, InPlace).is_ok() } else { true } @@ -347,7 +346,7 @@ impl RawVec { needed_extra_capacity: usize, ) -> Result<(), TryReserveError> { if self.needs_to_grow(used_capacity, needed_extra_capacity) { - self.grow(Exact, used_capacity, needed_extra_capacity, MayMove, Uninitialized) + self.grow_exact(used_capacity, needed_extra_capacity) } else { Ok(()) } @@ -372,13 +371,6 @@ impl RawVec { } } -#[derive(Copy, Clone)] -enum Strategy { - Amortized, - Exact, -} -use Strategy::*; - impl RawVec { /// Returns if the buffer needs to grow to fulfill the needed extra capacity. /// Mainly used to make inlining reserve-calls possible without inlining `grow`. @@ -396,54 +388,59 @@ impl RawVec { self.cap = Self::capacity_from_bytes(memory.size); } - /// Single method to handle all possibilities of growing the buffer. - fn grow( + // This method is usually instantiated many times. So we want it to be as + // small as possible, to improve compile times. But we also want as much of + // its contents to be statically computable as possible, to make the + // generated code run faster. Therefore, this method is carefully written + // so that all of the code that depends on `T` is within it, while as much + // of the code that doesn't depend on `T` as possible is in functions that + // are non-generic over `T`. + fn grow_amortized( &mut self, - strategy: Strategy, used_capacity: usize, needed_extra_capacity: usize, placement: ReallocPlacement, - init: AllocInit, ) -> Result<(), TryReserveError> { - let elem_size = mem::size_of::(); - if elem_size == 0 { + if mem::size_of::() == 0 { // Since we return a capacity of `usize::MAX` when `elem_size` is // 0, getting to here necessarily means the `RawVec` is overfull. return Err(CapacityOverflow); } - let new_layout = match strategy { - Amortized => { - // Nothing we can really do about these checks, sadly. - let required_cap = - used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; - // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`. - let double_cap = self.cap * 2; - // `double_cap` guarantees exponential growth. - let cap = cmp::max(double_cap, required_cap); - Layout::array::(cap).map_err(|_| CapacityOverflow)? - } - Exact => { - let cap = - used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; - Layout::array::(cap).map_err(|_| CapacityOverflow)? - } - }; - alloc_guard(new_layout.size())?; - let memory = if let Some((ptr, old_layout)) = self.current_memory() { - debug_assert_eq!(old_layout.align(), new_layout.align()); - unsafe { - self.alloc - .grow(ptr, old_layout, new_layout.size(), placement, init) - .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })? - } - } else { - match placement { - MayMove => self.alloc.alloc(new_layout, init), - InPlace => Err(AllocErr), - } - .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })? - }; + // Nothing we can really do about these checks, sadly. + let required_cap = + used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; + // Cannot overflow, because `cap <= isize::MAX`, and type of `cap` is `usize`. + let double_cap = self.cap * 2; + // `double_cap` guarantees exponential growth. + let cap = cmp::max(double_cap, required_cap); + let new_layout = Layout::array::(cap); + + // `finish_grow` is non-generic over `T`. + let memory = finish_grow(new_layout, placement, self.current_memory(), &mut self.alloc)?; + self.set_memory(memory); + Ok(()) + } + + // The constraints on this method are much the same as those on + // `grow_amortized`, but this method is usually instantiated less often so + // it's less critical. + fn grow_exact( + &mut self, + used_capacity: usize, + needed_extra_capacity: usize, + ) -> Result<(), TryReserveError> { + if mem::size_of::() == 0 { + // Since we return a capacity of `usize::MAX` when the type size is + // 0, getting to here necessarily means the `RawVec` is overfull. + return Err(CapacityOverflow); + } + + let cap = used_capacity.checked_add(needed_extra_capacity).ok_or(CapacityOverflow)?; + let new_layout = Layout::array::(cap); + + // `finish_grow` is non-generic over `T`. + let memory = finish_grow(new_layout, MayMove, self.current_memory(), &mut self.alloc)?; self.set_memory(memory); Ok(()) } @@ -471,6 +468,38 @@ impl RawVec { } } +// This function is outside `RawVec` to minimize compile times. See the comment +// above `RawVec::grow_amortized` for details. (The `A` parameter isn't +// significant, because the number of different `A` types seen in practice is +// much smaller than the number of `T` types.) +fn finish_grow( + new_layout: Result, + placement: ReallocPlacement, + current_memory: Option<(NonNull, Layout)>, + alloc: &mut A, +) -> Result +where + A: AllocRef, +{ + // Check for the error here to minimize the size of `RawVec::grow_*`. + let new_layout = new_layout.map_err(|_| CapacityOverflow)?; + + alloc_guard(new_layout.size())?; + + let memory = if let Some((ptr, old_layout)) = current_memory { + debug_assert_eq!(old_layout.align(), new_layout.align()); + unsafe { alloc.grow(ptr, old_layout, new_layout.size(), placement, Uninitialized) } + } else { + match placement { + MayMove => alloc.alloc(new_layout, Uninitialized), + InPlace => Err(AllocErr), + } + } + .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })?; + + Ok(memory) +} + impl RawVec { /// Converts the entire buffer into `Box<[MaybeUninit]>` with the specified `len`. /// -- cgit 1.4.1-3-g733a5 From dab3a5813e2590b2161d84a410e4d5bdc072152d Mon Sep 17 00:00:00 2001 From: Tomasz Miąsko Date: Thu, 14 May 2020 00:00:00 +0000 Subject: Fix Arc::decr_strong_count doc test --- src/liballoc/sync.rs | 8 +++++--- 1 file changed, 5 insertions(+), 3 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs index 19d289c87fd..dbee9d27d8a 100644 --- a/src/liballoc/sync.rs +++ b/src/liballoc/sync.rs @@ -835,12 +835,14 @@ impl Arc { /// /// unsafe { /// let ptr = Arc::into_raw(five); - /// Arc::decr_strong_count(ptr); + /// Arc::incr_strong_count(ptr); /// - /// // This assertion is deterministic because we haven't shared + /// // Those assertions are deterministic because we haven't shared /// // the `Arc` between threads. /// let five = Arc::from_raw(ptr); - /// assert_eq!(0, Arc::strong_count(&five)); + /// assert_eq!(2, Arc::strong_count(&five)); + /// Arc::decr_strong_count(ptr); + /// assert_eq!(1, Arc::strong_count(&five)); /// } /// ``` #[inline] -- cgit 1.4.1-3-g733a5 From 5980d972d1911225e38e98fe81974973349793a0 Mon Sep 17 00:00:00 2001 From: Ralf Jung Date: Sun, 17 May 2020 11:06:59 +0200 Subject: make abort intrinsic safe, and correct its documentation --- src/liballoc/rc.rs | 4 ++++ src/liballoc/sync.rs | 5 +++++ src/libcore/cell.rs | 5 ++--- src/libcore/intrinsics.rs | 2 +- src/libcore/panicking.rs | 18 +++++++++++++++--- src/libpanic_unwind/seh.rs | 5 ++++- src/librustc_typeck/check/intrinsic.rs | 6 ++++-- src/libstd/panicking.rs | 20 ++++++++++++++++---- src/libstd/sync/mpsc/shared.rs | 2 ++ src/libstd/sync/mpsc/sync.rs | 2 ++ 10 files changed, 55 insertions(+), 14 deletions(-) (limited to 'src/liballoc') diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs index 2f9505ec79f..0b2622b6ce3 100644 --- a/src/liballoc/rc.rs +++ b/src/liballoc/rc.rs @@ -2035,6 +2035,8 @@ trait RcBoxPtr { // nevertheless, we insert an abort here to hint LLVM at // an otherwise missed optimization. if strong == 0 || strong == usize::max_value() { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } @@ -2061,6 +2063,8 @@ trait RcBoxPtr { // nevertheless, we insert an abort here to hint LLVM at // an otherwise missed optimization. if weak == 0 || weak == usize::max_value() { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } diff --git a/src/liballoc/sync.rs b/src/liballoc/sync.rs index dbee9d27d8a..12232520ef4 100644 --- a/src/liballoc/sync.rs +++ b/src/liballoc/sync.rs @@ -1096,6 +1096,8 @@ impl Clone for Arc { // We abort because such a program is incredibly degenerate, and we // don't care to support it. if old_size > MAX_REFCOUNT { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } @@ -1614,6 +1616,8 @@ impl Weak { // See comments in `Arc::clone` for why we do this (for `mem::forget`). if n > MAX_REFCOUNT { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } @@ -1753,6 +1757,7 @@ impl Clone for Weak { // See comments in Arc::clone() for why we do this (for mem::forget). if old_size > MAX_REFCOUNT { + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump unsafe { abort(); } diff --git a/src/libcore/cell.rs b/src/libcore/cell.rs index 0f2665eba6f..fad3095f8a3 100644 --- a/src/libcore/cell.rs +++ b/src/libcore/cell.rs @@ -133,10 +133,9 @@ //! `Cell`. //! //! ``` -//! #![feature(core_intrinsics)] //! use std::cell::Cell; //! use std::ptr::NonNull; -//! use std::intrinsics::abort; +//! use std::process::abort; //! use std::marker::PhantomData; //! //! struct Rc { @@ -173,7 +172,7 @@ //! .strong //! .set(self.strong() //! .checked_add(1) -//! .unwrap_or_else(|| unsafe { abort() })); +//! .unwrap_or_else(|| abort() )); //! } //! } //! diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs index 962bcbe6198..43512f7a236 100644 --- a/src/libcore/intrinsics.rs +++ b/src/libcore/intrinsics.rs @@ -918,7 +918,7 @@ extern "rust-intrinsic" { /// Aborts the execution of the process. /// - /// The stabilized version of this intrinsic is + /// A more user-friendly and stable version of this operation is /// [`std::process::abort`](../../std/process/fn.abort.html). pub fn abort() -> !; diff --git a/src/libcore/panicking.rs b/src/libcore/panicking.rs index 94ea9b78828..16739b4a1af 100644 --- a/src/libcore/panicking.rs +++ b/src/libcore/panicking.rs @@ -39,8 +39,12 @@ use crate::panic::{Location, PanicInfo}; #[lang = "panic"] // needed by codegen for panic on overflow and other `Assert` MIR terminators pub fn panic(expr: &str) -> ! { if cfg!(feature = "panic_immediate_abort") { + // remove `unsafe` (and safety comment) on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // SAFETY: the `abort` intrinsic has no requirements to be called. - unsafe { super::intrinsics::abort() } + unsafe { + super::intrinsics::abort() + } } // Use Arguments::new_v1 instead of format_args!("{}", expr) to potentially @@ -58,8 +62,12 @@ pub fn panic(expr: &str) -> ! { #[lang = "panic_bounds_check"] // needed by codegen for panic on OOB array/slice access fn panic_bounds_check(index: usize, len: usize) -> ! { if cfg!(feature = "panic_immediate_abort") { + // remove `unsafe` (and safety comment) on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // SAFETY: the `abort` intrinsic has no requirements to be called. - unsafe { super::intrinsics::abort() } + unsafe { + super::intrinsics::abort() + } } panic!("index out of bounds: the len is {} but the index is {}", len, index) @@ -72,8 +80,12 @@ fn panic_bounds_check(index: usize, len: usize) -> ! { #[track_caller] pub fn panic_fmt(fmt: fmt::Arguments<'_>) -> ! { if cfg!(feature = "panic_immediate_abort") { + // remove `unsafe` (and safety comment) on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // SAFETY: the `abort` intrinsic has no requirements to be called. - unsafe { super::intrinsics::abort() } + unsafe { + super::intrinsics::abort() + } } // NOTE This function never crosses the FFI boundary; it's a Rust-to-Rust call diff --git a/src/libpanic_unwind/seh.rs b/src/libpanic_unwind/seh.rs index 8d8276b4159..b1e87a7cac2 100644 --- a/src/libpanic_unwind/seh.rs +++ b/src/libpanic_unwind/seh.rs @@ -327,5 +327,8 @@ pub unsafe fn cleanup(payload: *mut u8) -> Box { #[lang = "eh_personality"] #[cfg(not(test))] fn rust_eh_personality() { - unsafe { core::intrinsics::abort() } + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump + unsafe { + core::intrinsics::abort() + } } diff --git a/src/librustc_typeck/check/intrinsic.rs b/src/librustc_typeck/check/intrinsic.rs index 05028ff0b2c..db6c30adb04 100644 --- a/src/librustc_typeck/check/intrinsic.rs +++ b/src/librustc_typeck/check/intrinsic.rs @@ -69,7 +69,7 @@ fn equate_intrinsic_type<'tcx>( /// Returns `true` if the given intrinsic is unsafe to call or not. pub fn intrinsic_operation_unsafety(intrinsic: &str) -> hir::Unsafety { match intrinsic { - "size_of" | "min_align_of" | "needs_drop" | "caller_location" | "size_of_val" + "abort" | "size_of" | "min_align_of" | "needs_drop" | "caller_location" | "size_of_val" | "min_align_of_val" | "add_with_overflow" | "sub_with_overflow" | "mul_with_overflow" | "wrapping_add" | "wrapping_sub" | "wrapping_mul" | "saturating_add" | "saturating_sub" | "rotate_left" | "rotate_right" | "ctpop" | "ctlz" | "cttz" @@ -130,7 +130,9 @@ pub fn check_intrinsic_type(tcx: TyCtxt<'_>, it: &hir::ForeignItem<'_>) { } }; (n_tps, inputs, output, hir::Unsafety::Unsafe) - } else if &name[..] == "abort" || &name[..] == "unreachable" { + } else if &name[..] == "abort" { + (0, Vec::new(), tcx.types.never, hir::Unsafety::Normal) + } else if &name[..] == "unreachable" { (0, Vec::new(), tcx.types.never, hir::Unsafety::Unsafe) } else { let unsafety = intrinsic_operation_unsafety(&name[..]); diff --git a/src/libstd/panicking.rs b/src/libstd/panicking.rs index 343b2ee1273..bf381896a22 100644 --- a/src/libstd/panicking.rs +++ b/src/libstd/panicking.rs @@ -332,7 +332,10 @@ pub fn panicking() -> bool { #[cfg_attr(feature = "panic_immediate_abort", inline)] pub fn begin_panic_fmt(msg: &fmt::Arguments<'_>) -> ! { if cfg!(feature = "panic_immediate_abort") { - unsafe { intrinsics::abort() } + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump + unsafe { + intrinsics::abort() + } } let info = PanicInfo::internal_constructor(Some(msg), Location::caller()); @@ -398,7 +401,10 @@ pub fn begin_panic_handler(info: &PanicInfo<'_>) -> ! { #[track_caller] pub fn begin_panic(msg: M) -> ! { if cfg!(feature = "panic_immediate_abort") { - unsafe { intrinsics::abort() } + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump + unsafe { + intrinsics::abort() + } } rust_panic_with_hook(&mut PanicPayload::new(msg), None, Location::caller()); @@ -458,7 +464,10 @@ fn rust_panic_with_hook( "thread panicked while processing \ panic. aborting.\n" )); - unsafe { intrinsics::abort() } + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump + unsafe { + intrinsics::abort() + } } unsafe { @@ -493,7 +502,10 @@ fn rust_panic_with_hook( "thread panicked while panicking. \ aborting.\n" )); - unsafe { intrinsics::abort() } + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // remove `unsafe` on bootstrap bump + unsafe { + intrinsics::abort() + } } rust_panic(payload) diff --git a/src/libstd/sync/mpsc/shared.rs b/src/libstd/sync/mpsc/shared.rs index fd9d61e99c2..d1a46c51757 100644 --- a/src/libstd/sync/mpsc/shared.rs +++ b/src/libstd/sync/mpsc/shared.rs @@ -354,6 +354,8 @@ impl Packet { // See comments on Arc::clone() on why we do this (for `mem::forget`). if old_count > MAX_REFCOUNT { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } diff --git a/src/libstd/sync/mpsc/sync.rs b/src/libstd/sync/mpsc/sync.rs index 79123903e92..603764922c5 100644 --- a/src/libstd/sync/mpsc/sync.rs +++ b/src/libstd/sync/mpsc/sync.rs @@ -358,6 +358,8 @@ impl Packet { // See comments on Arc::clone() on why we do this (for `mem::forget`). if old_count > MAX_REFCOUNT { + // remove `unsafe` on bootstrap bump + #[cfg_attr(not(bootstrap), allow(unused_unsafe))] unsafe { abort(); } -- cgit 1.4.1-3-g733a5