diff options
Diffstat (limited to 'library/alloc/src')
| -rw-r--r-- | library/alloc/src/alloc.rs | 4 | ||||
| -rw-r--r-- | library/alloc/src/collections/binary_heap/mod.rs (renamed from library/alloc/src/collections/binary_heap.rs) | 89 | ||||
| -rw-r--r-- | library/alloc/src/collections/binary_heap/tests.rs | 38 | ||||
| -rw-r--r-- | library/alloc/src/lib.rs | 1 | ||||
| -rw-r--r-- | library/alloc/src/rc.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/sync.rs | 8 | ||||
| -rw-r--r-- | library/alloc/src/vec/into_iter.rs | 6 | ||||
| -rw-r--r-- | library/alloc/src/vec/is_zero.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/vec/mod.rs | 4 |
9 files changed, 125 insertions, 29 deletions
diff --git a/library/alloc/src/alloc.rs b/library/alloc/src/alloc.rs index fe6de1cf879..3a797bd5eca 100644 --- a/library/alloc/src/alloc.rs +++ b/library/alloc/src/alloc.rs @@ -20,7 +20,7 @@ use core::marker::Destruct; mod tests; extern "Rust" { - // These are the magic symbols to call the global allocator. rustc generates + // These are the magic symbols to call the global allocator. rustc generates // them to call `__rg_alloc` etc. if there is a `#[global_allocator]` attribute // (the code expanding that attribute macro generates those functions), or to call // the default implementations in std (`__rdl_alloc` etc. in `library/std/src/alloc.rs`) @@ -353,7 +353,7 @@ pub(crate) const unsafe fn box_free<T: ?Sized, A: ~const Allocator + ~const Dest #[cfg(not(no_global_oom_handling))] extern "Rust" { - // This is the magic symbol to call the global alloc error handler. rustc generates + // This is the magic symbol to call the global alloc error handler. rustc generates // it to call `__rg_oom` if there is a `#[alloc_error_handler]`, or to call the // default implementations below (`__rdl_oom`) otherwise. fn __rust_alloc_error_handler(size: usize, align: usize) -> !; diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap/mod.rs index 4583bc9a158..f1d0a305d99 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -146,6 +146,7 @@ use core::fmt; use core::iter::{FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; +use core::num::NonZeroUsize; use core::ops::{Deref, DerefMut}; use core::ptr; @@ -165,12 +166,20 @@ mod tests; /// It is a logic error for an item to be modified in such a way that the /// item's ordering relative to any other item, as determined by the [`Ord`] /// trait, changes while it is in the heap. This is normally only possible -/// through [`Cell`], [`RefCell`], global state, I/O, or unsafe code. The +/// through interior mutability, global state, I/O, or unsafe code. The /// behavior resulting from such a logic error is not specified, but will /// be encapsulated to the `BinaryHeap` that observed the logic error and not /// result in undefined behavior. This could include panics, incorrect results, /// aborts, memory leaks, and non-termination. /// +/// As long as no elements change their relative order while being in the heap +/// as described above, the API of `BinaryHeap` guarantees that the heap +/// invariant remains intact i.e. its methods all behave as documented. For +/// example if a method is documented as iterating in sorted order, that's +/// guaranteed to work as long as elements in the heap have not changed order, +/// even in the presence of closures getting unwinded out of, iterators getting +/// leaked, and similar foolishness. +/// /// # Examples /// /// ``` @@ -279,7 +288,9 @@ pub struct BinaryHeap<T> { #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub struct PeekMut<'a, T: 'a + Ord> { heap: &'a mut BinaryHeap<T>, - sift: bool, + // If a set_len + sift_down are required, this is Some. If a &mut T has not + // yet been exposed to peek_mut()'s caller, it's None. + original_len: Option<NonZeroUsize>, } #[stable(feature = "collection_debug", since = "1.17.0")] @@ -292,7 +303,14 @@ impl<T: Ord + fmt::Debug> fmt::Debug for PeekMut<'_, T> { #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] impl<T: Ord> Drop for PeekMut<'_, T> { fn drop(&mut self) { - if self.sift { + if let Some(original_len) = self.original_len { + // SAFETY: That's how many elements were in the Vec at the time of + // the PeekMut::deref_mut call, and therefore also at the time of + // the BinaryHeap::peek_mut call. Since the PeekMut did not end up + // getting leaked, we are now undoing the leak amplification that + // the DerefMut prepared for. + unsafe { self.heap.data.set_len(original_len.get()) }; + // SAFETY: PeekMut is only instantiated for non-empty heaps. unsafe { self.heap.sift_down(0) }; } @@ -313,7 +331,26 @@ impl<T: Ord> Deref for PeekMut<'_, T> { impl<T: Ord> DerefMut for PeekMut<'_, T> { fn deref_mut(&mut self) -> &mut T { debug_assert!(!self.heap.is_empty()); - self.sift = true; + + let len = self.heap.len(); + if len > 1 { + // Here we preemptively leak all the rest of the underlying vector + // after the currently max element. If the caller mutates the &mut T + // we're about to give them, and then leaks the PeekMut, all these + // elements will remain leaked. If they don't leak the PeekMut, then + // either Drop or PeekMut::pop will un-leak the vector elements. + // + // This is technique is described throughout several other places in + // the standard library as "leak amplification". + unsafe { + // SAFETY: len > 1 so len != 0. + self.original_len = Some(NonZeroUsize::new_unchecked(len)); + // SAFETY: len > 1 so all this does for now is leak elements, + // which is safe. + self.heap.data.set_len(1); + } + } + // SAFE: PeekMut is only instantiated for non-empty heaps unsafe { self.heap.data.get_unchecked_mut(0) } } @@ -323,9 +360,16 @@ impl<'a, T: Ord> PeekMut<'a, T> { /// Removes the peeked value from the heap and returns it. #[stable(feature = "binary_heap_peek_mut_pop", since = "1.18.0")] pub fn pop(mut this: PeekMut<'a, T>) -> T { - let value = this.heap.pop().unwrap(); - this.sift = false; - value + if let Some(original_len) = this.original_len.take() { + // SAFETY: This is how many elements were in the Vec at the time of + // the BinaryHeap::peek_mut call. + unsafe { this.heap.data.set_len(original_len.get()) }; + + // Unlike in Drop, here we don't also need to do a sift_down even if + // the caller could've mutated the element. It is removed from the + // heap on the next line and pop() is not sensitive to its value. + } + this.heap.pop().unwrap() } } @@ -398,8 +442,9 @@ impl<T: Ord> BinaryHeap<T> { /// Returns a mutable reference to the greatest item in the binary heap, or /// `None` if it is empty. /// - /// Note: If the `PeekMut` value is leaked, the heap may be in an - /// inconsistent state. + /// Note: If the `PeekMut` value is leaked, some heap elements might get + /// leaked along with it, but the remaining elements will remain a valid + /// heap. /// /// # Examples /// @@ -426,7 +471,7 @@ impl<T: Ord> BinaryHeap<T> { /// otherwise it's *O*(1). #[stable(feature = "binary_heap_peek_mut", since = "1.12.0")] pub fn peek_mut(&mut self) -> Option<PeekMut<'_, T>> { - if self.is_empty() { None } else { Some(PeekMut { heap: self, sift: false }) } + if self.is_empty() { None } else { Some(PeekMut { heap: self, original_len: None }) } } /// Removes the greatest item from the binary heap and returns it, or `None` if it @@ -806,18 +851,30 @@ impl<T: Ord> BinaryHeap<T> { where F: FnMut(&T) -> bool, { - let mut first_removed = self.len(); + struct RebuildOnDrop<'a, T: Ord> { + heap: &'a mut BinaryHeap<T>, + first_removed: usize, + } + + let mut guard = RebuildOnDrop { first_removed: self.len(), heap: self }; + let mut i = 0; - self.data.retain(|e| { + guard.heap.data.retain(|e| { let keep = f(e); - if !keep && i < first_removed { - first_removed = i; + if !keep && i < guard.first_removed { + guard.first_removed = i; } i += 1; keep }); - // data[0..first_removed] is untouched, so we only need to rebuild the tail: - self.rebuild_tail(first_removed); + + impl<'a, T: Ord> Drop for RebuildOnDrop<'a, T> { + fn drop(&mut self) { + // data[..first_removed] is untouched, so we only need to + // rebuild the tail: + self.heap.rebuild_tail(self.first_removed); + } + } } } diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index 59c516374c0..500caa35678 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,6 +1,7 @@ use super::*; use crate::boxed::Box; use crate::testing::crash_test::{CrashTestDummy, Panic}; +use core::mem; use std::iter::TrustedLen; use std::panic::{catch_unwind, AssertUnwindSafe}; @@ -147,6 +148,24 @@ fn test_peek_mut() { } #[test] +fn test_peek_mut_leek() { + let data = vec![4, 2, 7]; + let mut heap = BinaryHeap::from(data); + let mut max = heap.peek_mut().unwrap(); + *max = -1; + + // The PeekMut object's Drop impl would have been responsible for moving the + // -1 out of the max position of the BinaryHeap, but we don't run it. + mem::forget(max); + + // Absent some mitigation like leak amplification, the -1 would incorrectly + // end up in the last position of the returned Vec, with the rest of the + // heap's original contents in front of it in sorted order. + let sorted_vec = heap.into_sorted_vec(); + assert!(sorted_vec.is_sorted(), "{:?}", sorted_vec); +} + +#[test] fn test_peek_mut_pop() { let data = vec![2, 4, 6, 2, 1, 8, 10, 3, 5, 7, 0, 9, 1]; let mut heap = BinaryHeap::from(data); @@ -455,6 +474,25 @@ fn test_retain() { assert!(a.is_empty()); } +#[test] +fn test_retain_catch_unwind() { + let mut heap = BinaryHeap::from(vec![3, 1, 2]); + + // Removes the 3, then unwinds out of retain. + let _ = catch_unwind(AssertUnwindSafe(|| { + heap.retain(|e| { + if *e == 1 { + panic!(); + } + false + }); + })); + + // Naively this would be [1, 2] (an invalid heap) if BinaryHeap delegates to + // Vec's retain impl and then does not rebuild the heap after that unwinds. + assert_eq!(heap.into_vec(), [2, 1]); +} + // old binaryheap failed this test // // Integrity means that all elements are present after a comparison panics, diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 4e812529c2c..afc3a3dc6a8 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -125,6 +125,7 @@ #![feature(hasher_prefixfree_extras)] #![feature(inline_const)] #![feature(inplace_iteration)] +#![cfg_attr(test, feature(is_sorted))] #![feature(iter_advance_by)] #![feature(iter_next_chunk)] #![feature(iter_repeat_n)] diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs index c1d853ed652..c9aa23fc4af 100644 --- a/library/alloc/src/rc.rs +++ b/library/alloc/src/rc.rs @@ -2179,7 +2179,7 @@ pub struct Weak<T: ?Sized> { // This is a `NonNull` to allow optimizing the size of this type in enums, // but it is not necessarily a valid pointer. // `Weak::new` sets this to `usize::MAX` so that it doesn’t need - // to allocate space on the heap. That's not a value a real pointer + // to allocate space on the heap. That's not a value a real pointer // will ever have because RcBox has alignment at least 2. // This is only possible when `T: Sized`; unsized `T` never dangle. ptr: NonNull<RcBox<T>>, diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index d833d4d1dfb..bab7f5f5365 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -295,7 +295,7 @@ pub struct Weak<T: ?Sized> { // This is a `NonNull` to allow optimizing the size of this type in enums, // but it is not necessarily a valid pointer. // `Weak::new` sets this to `usize::MAX` so that it doesn’t need - // to allocate space on the heap. That's not a value a real pointer + // to allocate space on the heap. That's not a value a real pointer // will ever have because RcBox has alignment at least 2. // This is only possible when `T: Sized`; unsized `T` never dangle. ptr: NonNull<ArcInner<T>>, @@ -1656,7 +1656,7 @@ impl<T: ?Sized> Arc<T> { // // The acquire label here ensures a happens-before relationship with any // writes to `strong` (in particular in `Weak::upgrade`) prior to decrements - // of the `weak` count (via `Weak::drop`, which uses release). If the upgraded + // of the `weak` count (via `Weak::drop`, which uses release). If the upgraded // weak ref was never dropped, the CAS here will fail so we do not care to synchronize. if self.inner().weak.compare_exchange(1, usize::MAX, Acquire, Relaxed).is_ok() { // This needs to be an `Acquire` to synchronize with the decrement of the `strong` @@ -1712,7 +1712,7 @@ unsafe impl<#[may_dangle] T: ?Sized> Drop for Arc<T> { } // This fence is needed to prevent reordering of use of the data and - // deletion of the data. Because it is marked `Release`, the decreasing + // deletion of the data. Because it is marked `Release`, the decreasing // of the reference count synchronizes with this `Acquire` fence. This // means that use of the data happens before decreasing the reference // count, which happens before this fence, which happens before the @@ -2172,7 +2172,7 @@ impl<T: ?Sized> Clone for Weak<T> { } else { return Weak { ptr: self.ptr }; }; - // See comments in Arc::clone() for why this is relaxed. This can use a + // See comments in Arc::clone() for why this is relaxed. This can use a // fetch_add (ignoring the lock) because the weak count is only locked // where are *no other* weak pointers in existence. (So we can't be // running this code in that case). diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index b207b3210f1..37966007eb7 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -40,7 +40,7 @@ pub struct IntoIter< // to avoid dropping the allocator twice we need to wrap it into ManuallyDrop pub(super) alloc: ManuallyDrop<A>, pub(super) ptr: *const T, - pub(super) end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that + 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. } @@ -146,9 +146,9 @@ impl<T, A: Allocator> IntoIter<T, A> { 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`, + // 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. + // 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 { diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs index 8e652d676dc..26120270c0c 100644 --- a/library/alloc/src/vec/is_zero.rs +++ b/library/alloc/src/vec/is_zero.rs @@ -57,7 +57,7 @@ unsafe impl<T: IsZero, const N: usize> 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 diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 36cfac8ee9e..36b0b3c9e7c 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -2429,7 +2429,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> { 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); } @@ -2686,7 +2686,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> { // 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 { |