src/liballoc/raw_vec.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use core::ptr::Unique;
  12 use core::mem;
  13 use core::slice::{self, SliceExt};
  14 use heap;
  15 use super::oom;
  16 use super::boxed::Box;
  17 use core::ops::Drop;
  18 use core;
  19
  20 /// A low-level utility for more ergonomically allocating, reallocating, and deallocating a
  21 /// a buffer of memory on the heap without having to worry about all the corner cases
  22 /// involved. This type is excellent for building your own data structures like Vec and VecDeque.
  23 /// In particular:
  24 ///
  25 /// * Produces heap::EMPTY on zero-sized types
  26 /// * Produces heap::EMPTY on zero-length allocations
  27 /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics)
  28 /// * Guards against 32-bit systems allocating more than isize::MAX bytes
  29 /// * Guards against overflowing your length
  30 /// * Aborts on OOM
  31 /// * Avoids freeing heap::EMPTY
  32 /// * Contains a ptr::Unique and thus endows the user with all related benefits
  33 ///
  34 /// This type does not in anyway inspect the memory that it manages. When dropped it *will*
  35 /// free its memory, but it *won't* try to Drop its contents. It is up to the user of RawVec
  36 /// to handle the actual things *stored* inside of a RawVec.
  37 ///
  38 /// Note that a RawVec always forces its capacity to be usize::MAX for zero-sized types.
  39 /// This enables you to use capacity growing logic catch the overflows in your length
  40 /// that might occur with zero-sized types.
  41 ///
  42 /// However this means that you need to be careful when roundtripping this type
  43 /// with a `Box<[T]>`: `cap()` won't yield the len. However `with_capacity`,
  44 /// `shrink_to_fit`, and `from_box` will actually set RawVec's private capacity
  45 /// field. This allows zero-sized types to not be special-cased by consumers of
  46 /// this type.
  47 #[unsafe_no_drop_flag]
  48 pub struct RawVec<T> {
  49     ptr: Unique<T>,
  50     cap: usize,
  51 }
  52
  53 impl<T> RawVec<T> {
  54     /// Creates the biggest possible RawVec without allocating. If T has positive
  55     /// size, then this makes a RawVec with capacity 0. If T has 0 size, then it
  56     /// it makes a RawVec with capacity `usize::MAX`. Useful for implementing
  57     /// delayed allocation.
  58     pub fn new() -> Self {
  59         unsafe {
  60             // !0 is usize::MAX. This branch should be stripped at compile time.
  61             let cap = if mem::size_of::<T>() == 0 {
  62                 !0
  63             } else {
  64                 0
  65             };
  66
  67             // heap::EMPTY doubles as "unallocated" and "zero-sized allocation"
  68             RawVec { ptr: Unique::new(heap::EMPTY as *mut T), cap: cap }
  69         }
  70     }
  71
  72     /// Creates a RawVec with exactly the capacity and alignment requirements
  73     /// for a `[T; cap]`. This is equivalent to calling RawVec::new when `cap` is 0
  74     /// or T is zero-sized. Note that if `T` is zero-sized this means you will *not*
  75     /// get a RawVec with the requested capacity!
  76     ///
  77     /// # Panics
  78     ///
  79     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
  80     /// * Panics on 32-bit platforms if the requested capacity exceeds
  81     ///   `isize::MAX` bytes.
  82     ///
  83     /// # Aborts
  84     ///
  85     /// Aborts on OOM
  86     pub fn with_capacity(cap: usize) -> Self {
  87         unsafe {
  88             let elem_size = mem::size_of::<T>();
  89
  90             let alloc_size = cap.checked_mul(elem_size).expect("capacity overflow");
  91             alloc_guard(alloc_size);
  92
  93             // handles ZSTs and `cap = 0` alike
  94             let ptr = if alloc_size == 0 {
  95                 heap::EMPTY as *mut u8
  96             } else {
  97                 let align = mem::align_of::<T>();
  98                 let ptr = heap::allocate(alloc_size, align);
  99                 if ptr.is_null() {
 100                     oom()
 101                 }
 102                 ptr
 103             };
 104
 105             RawVec { ptr: Unique::new(ptr as *mut _), cap: cap }
 106         }
 107     }
 108
 109     /// Reconstitutes a RawVec from a pointer and capacity.
 110     ///
 111     /// # Undefined Behaviour
 112     ///
 113     /// The ptr must be allocated, and with the given capacity. The
 114     /// capacity cannot exceed `isize::MAX` (only a concern on 32-bit systems).
 115     /// If the ptr and capacity come from a RawVec, then this is guaranteed.
 116     pub unsafe fn from_raw_parts(ptr: *mut T, cap: usize) -> Self {
 117         RawVec { ptr: Unique::new(ptr), cap: cap }
 118     }
 119
 120     /// Converts a `Box<[T]>` into a `RawVec<T>`.
 121     pub fn from_box(mut slice: Box<[T]>) -> Self {
 122         unsafe {
 123             let result = RawVec::from_raw_parts(slice.as_mut_ptr(), slice.len());
 124             mem::forget(slice);
 125             result
 126         }
 127     }
 128 }
 129
 130 impl<T> RawVec<T> {
 131     /// Gets a raw pointer to the start of the allocation. Note that this is
 132     /// heap::EMPTY if `cap = 0` or T is zero-sized. In the former case, you must
 133     /// be careful.
 134     pub fn ptr(&self) -> *mut T {
 135         *self.ptr
 136     }
 137
 138     /// Gets the capacity of the allocation.
 139     ///
 140     /// This will always be `usize::MAX` if `T` is zero-sized.
 141     pub fn cap(&self) -> usize {
 142         if mem::size_of::<T>() == 0 {
 143             !0
 144         } else {
 145             self.cap
 146         }
 147     }
 148
 149     /// Doubles the size of the type's backing allocation. This is common enough
 150     /// to want to do that it's easiest to just have a dedicated method. Slightly
 151     /// more efficient logic can be provided for this than the general case.
 152     ///
 153     /// This function is ideal for when pushing elements one-at-a-time because
 154     /// you don't need to incur the costs of the more general computations
 155     /// reserve needs to do to guard against overflow. You do however need to
 156     /// manually check if your `len == cap`.
 157     ///
 158     /// # Panics
 159     ///
 160     /// * Panics if T is zero-sized on the assumption that you managed to exhaust
 161     ///   all `usize::MAX` slots in your imaginary buffer.
 162     /// * Panics on 32-bit platforms if the requested capacity exceeds
 163     ///   `isize::MAX` bytes.
 164     ///
 165     /// # Aborts
 166     ///
 167     /// Aborts on OOM
 168     ///
 169     /// # Examples
 170     ///
 171     /// ```ignore
 172     /// struct MyVec<T> {
 173     ///     buf: RawVec<T>,
 174     ///     len: usize,
 175     /// }
 176     ///
 177     /// impl<T> MyVec<T> {
 178     ///     pub fn push(&mut self, elem: T) {
 179     ///         if self.len == self.buf.cap() { self.buf.double(); }
 180     ///         // double would have aborted or panicked if the len exceeded
 181     ///         // `isize::MAX` so this is safe to do unchecked now.
 182     ///         unsafe {
 183     ///             ptr::write(self.buf.ptr().offset(self.len as isize), elem);
 184     ///         }
 185     ///         self.len += 1;
 186     ///     }
 187     /// }
 188     /// ```
 189     #[inline(never)]
 190     #[cold]
 191     pub fn double(&mut self) {
 192         unsafe {
 193             let elem_size = mem::size_of::<T>();
 194
 195             // since we set the capacity to usize::MAX when elem_size is
 196             // 0, getting to here necessarily means the RawVec is overfull.
 197             assert!(elem_size != 0, "capacity overflow");
 198
 199             let align = mem::align_of::<T>();
 200
 201             let (new_cap, ptr) = if self.cap == 0 {
 202                 // skip to 4 because tiny Vec's are dumb; but not if that would cause overflow
 203                 let new_cap = if elem_size > (!0) / 8 {
 204                     1
 205                 } else {
 206                     4
 207                 };
 208                 let ptr = heap::allocate(new_cap * elem_size, align);
 209                 (new_cap, ptr)
 210             } else {
 211                 // Since we guarantee that we never allocate more than isize::MAX bytes,
 212                 // `elem_size * self.cap <= isize::MAX` as a precondition, so this can't overflow
 213                 let new_cap = 2 * self.cap;
 214                 let new_alloc_size = new_cap * elem_size;
 215                 alloc_guard(new_alloc_size);
 216                 let ptr = heap::reallocate(self.ptr() as *mut _,
 217                                            self.cap * elem_size,
 218                                            new_alloc_size,
 219                                            align);
 220                 (new_cap, ptr)
 221             };
 222
 223             // If allocate or reallocate fail, we'll get `null` back
 224             if ptr.is_null() {
 225                 oom()
 226             }
 227
 228             self.ptr = Unique::new(ptr as *mut _);
 229             self.cap = new_cap;
 230         }
 231     }
 232
 233     /// Ensures that the buffer contains at least enough space to hold
 234     /// `used_cap + needed_extra_cap` elements. If it doesn't already,
 235     /// will reallocate the minimum possible amount of memory necessary.
 236     /// Generally this will be exactly the amount of memory necessary,
 237     /// but in principle the allocator is free to give back more than
 238     /// we asked for.
 239     ///
 240     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
 241     /// the requested space. This is not really unsafe, but the unsafe
 242     /// code *you* write that relies on the behaviour of this function may break.
 243     ///
 244     /// # Panics
 245     ///
 246     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 247     /// * Panics on 32-bit platforms if the requested capacity exceeds
 248     ///   `isize::MAX` bytes.
 249     ///
 250     /// # Aborts
 251     ///
 252     /// Aborts on OOM
 253     pub fn reserve_exact(&mut self, used_cap: usize, needed_extra_cap: usize) {
 254         unsafe {
 255             let elem_size = mem::size_of::<T>();
 256             let align = mem::align_of::<T>();
 257
 258             // NOTE: we don't early branch on ZSTs here because we want this
 259             // to actually catch "asking for more than usize::MAX" in that case.
 260             // If we make it past the first branch then we are guaranteed to
 261             // panic.
 262
 263             // Don't actually need any more capacity.
 264             // Wrapping in case they gave a bad `used_cap`.
 265             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
 266                 return;
 267             }
 268
 269             // Nothing we can really do about these checks :(
 270             let new_cap = used_cap.checked_add(needed_extra_cap).expect("capacity overflow");
 271             let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
 272             alloc_guard(new_alloc_size);
 273
 274             let ptr = if self.cap == 0 {
 275                 heap::allocate(new_alloc_size, align)
 276             } else {
 277                 heap::reallocate(self.ptr() as *mut _,
 278                                  self.cap * elem_size,
 279                                  new_alloc_size,
 280                                  align)
 281             };
 282
 283             // If allocate or reallocate fail, we'll get `null` back
 284             if ptr.is_null() {
 285                 oom()
 286             }
 287
 288             self.ptr = Unique::new(ptr as *mut _);
 289             self.cap = new_cap;
 290         }
 291     }
 292
 293     /// Ensures that the buffer contains at least enough space to hold
 294     /// `used_cap + needed_extra_cap` elements. If it doesn't already have
 295     /// enough capacity, will reallocate enough space plus comfortable slack
 296     /// space to get amortized `O(1)` behaviour. Will limit this behaviour
 297     /// if it would needlessly cause itself to panic.
 298     ///
 299     /// If `used_cap` exceeds `self.cap()`, this may fail to actually allocate
 300     /// the requested space. This is not really unsafe, but the unsafe
 301     /// code *you* write that relies on the behaviour of this function may break.
 302     ///
 303     /// This is ideal for implementing a bulk-push operation like `extend`.
 304     ///
 305     /// # Panics
 306     ///
 307     /// * Panics if the requested capacity exceeds `usize::MAX` bytes.
 308     /// * Panics on 32-bit platforms if the requested capacity exceeds
 309     ///   `isize::MAX` bytes.
 310     ///
 311     /// # Aborts
 312     ///
 313     /// Aborts on OOM
 314     ///
 315     /// # Examples
 316     ///
 317     /// ```ignore
 318     /// struct MyVec<T> {
 319     ///     buf: RawVec<T>,
 320     ///     len: usize,
 321     /// }
 322     ///
 323     /// impl<T> MyVec<T> {
 324     ///     pub fn push_all(&mut self, elems: &[T]) {
 325     ///         self.buf.reserve(self.len, elems.len());
 326     ///         // reserve would have aborted or panicked if the len exceeded
 327     ///         // `isize::MAX` so this is safe to do unchecked now.
 328     ///         for x in elems {
 329     ///             unsafe {
 330     ///                 ptr::write(self.buf.ptr().offset(self.len as isize), x.clone());
 331     ///             }
 332     ///             self.len += 1;
 333     ///         }
 334     ///     }
 335     /// }
 336     /// ```
 337     pub fn reserve(&mut self, used_cap: usize, needed_extra_cap: usize) {
 338         unsafe {
 339             let elem_size = mem::size_of::<T>();
 340             let align = mem::align_of::<T>();
 341
 342             // NOTE: we don't early branch on ZSTs here because we want this
 343             // to actually catch "asking for more than usize::MAX" in that case.
 344             // If we make it past the first branch then we are guaranteed to
 345             // panic.
 346
 347             // Don't actually need any more capacity.
 348             // Wrapping in case they give a bas `used_cap`
 349             if self.cap().wrapping_sub(used_cap) >= needed_extra_cap {
 350                 return;
 351             }
 352
 353             // Nothing we can really do about these checks :(
 354             let new_cap = used_cap.checked_add(needed_extra_cap)
 355                                   .and_then(|cap| cap.checked_mul(2))
 356                                   .expect("capacity overflow");
 357             let new_alloc_size = new_cap.checked_mul(elem_size).expect("capacity overflow");
 358             // FIXME: may crash and burn on over-reserve
 359             alloc_guard(new_alloc_size);
 360
 361             let ptr = if self.cap == 0 {
 362                 heap::allocate(new_alloc_size, align)
 363             } else {
 364                 heap::reallocate(self.ptr() as *mut _,
 365                                  self.cap * elem_size,
 366                                  new_alloc_size,
 367                                  align)
 368             };
 369
 370             // If allocate or reallocate fail, we'll get `null` back
 371             if ptr.is_null() {
 372                 oom()
 373             }
 374
 375             self.ptr = Unique::new(ptr as *mut _);
 376             self.cap = new_cap;
 377         }
 378     }
 379
 380     /// Shrinks the allocation down to the specified amount. If the given amount
 381     /// is 0, actually completely deallocates.
 382     ///
 383     /// # Panics
 384     ///
 385     /// Panics if the given amount is *larger* than the current capacity.
 386     ///
 387     /// # Aborts
 388     ///
 389     /// Aborts on OOM.
 390     pub fn shrink_to_fit(&mut self, amount: usize) {
 391         let elem_size = mem::size_of::<T>();
 392         let align = mem::align_of::<T>();
 393
 394         // Set the `cap` because they might be about to promote to a `Box<[T]>`
 395         if elem_size == 0 {
 396             self.cap = amount;
 397             return;
 398         }
 399
 400         // This check is my waterloo; it's the only thing Vec wouldn't have to do.
 401         assert!(self.cap >= amount,
 402                 "Tried to shrink to a larger capacity");
 403
 404         if amount == 0 {
 405             mem::replace(self, RawVec::new());
 406         } else if self.cap != amount {
 407             unsafe {
 408                 // Overflow check is unnecessary as the vector is already at
 409                 // least this large.
 410                 let ptr = heap::reallocate(self.ptr() as *mut _,
 411                                            self.cap * elem_size,
 412                                            amount * elem_size,
 413                                            align);
 414                 if ptr.is_null() {
 415                     oom()
 416                 }
 417                 self.ptr = Unique::new(ptr as *mut _);
 418             }
 419             self.cap = amount;
 420         }
 421     }
 422
 423     /// Converts the entire buffer into `Box<[T]>`.
 424     ///
 425     /// While it is not *strictly* Undefined Behaviour to call
 426     /// this procedure while some of the RawVec is unintialized,
 427     /// it cetainly makes it trivial to trigger it.
 428     ///
 429     /// Note that this will correctly reconstitute any `cap` changes
 430     /// that may have been performed. (see description of type for details)
 431     pub unsafe fn into_box(self) -> Box<[T]> {
 432         // NOTE: not calling `cap()` here, actually using the real `cap` field!
 433         let slice = slice::from_raw_parts_mut(self.ptr(), self.cap);
 434         let output: Box<[T]> = Box::from_raw(slice);
 435         mem::forget(self);
 436         output
 437     }
 438
 439     /// This is a stupid name in the hopes that someone will find this in the
 440     /// not too distant future and remove it with the rest of
 441     /// #[unsafe_no_drop_flag]
 442     pub fn unsafe_no_drop_flag_needs_drop(&self) -> bool {
 443         self.cap != mem::POST_DROP_USIZE
 444     }
 445 }
 446
 447 impl<T> Drop for RawVec<T> {
 448     /// Frees the memory owned by the RawVec *without* trying to Drop its contents.
 449     fn drop(&mut self) {
 450         let elem_size = mem::size_of::<T>();
 451         if elem_size != 0 && self.cap != 0 && self.unsafe_no_drop_flag_needs_drop() {
 452             let align = mem::align_of::<T>();
 453
 454             let num_bytes = elem_size * self.cap;
 455             unsafe {
 456                 heap::deallocate(*self.ptr as *mut _, num_bytes, align);
 457             }
 458         }
 459     }
 460 }
 461
 462
 463
 464 // We need to guarantee the following:
 465 // * We don't ever allocate `> isize::MAX` byte-size objects
 466 // * We don't overflow `usize::MAX` and actually allocate too little
 467 //
 468 // On 64-bit we just need to check for overflow since trying to allocate
 469 // `> isize::MAX` bytes will surely fail. On 32-bit we need to add an extra
 470 // guard for this in case we're running on a platform which can use all 4GB in
 471 // user-space. e.g. PAE or x32
 472
 473 #[inline]
 474 fn alloc_guard(alloc_size: usize) {
 475     if core::usize::BITS < 64 {
 476         assert!(alloc_size <= ::core::isize::MAX as usize,
 477                 "capacity overflow");
 478     }
 479 }