src/libcore/alloc.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 //! Memory allocation APIs
  12
  13 #![stable(feature = "alloc_module", since = "1.28.0")]
  14
  15 use cmp;
  16 use fmt;
  17 use mem;
  18 use usize;
  19 use ptr::{self, NonNull};
  20 use num::NonZeroUsize;
  21
  22 #[unstable(feature = "alloc_internals", issue = "0")]
  23 #[cfg(stage0)]
  24 pub type Opaque = u8;
  25
  26 /// Represents the combination of a starting address and
  27 /// a total capacity of the returned block.
  28 #[unstable(feature = "allocator_api", issue = "32838")]
  29 #[derive(Debug)]
  30 pub struct Excess(pub NonNull<u8>, pub usize);
  31
  32 fn size_align<T>() -> (usize, usize) {
  33     (mem::size_of::<T>(), mem::align_of::<T>())
  34 }
  35
  36 /// Layout of a block of memory.
  37 ///
  38 /// An instance of `Layout` describes a particular layout of memory.
  39 /// You build a `Layout` up as an input to give to an allocator.
  40 ///
  41 /// All layouts have an associated non-negative size and a
  42 /// power-of-two alignment.
  43 ///
  44 /// (Note however that layouts are *not* required to have positive
  45 /// size, even though many allocators require that all memory
  46 /// requests have positive size. A caller to the `Alloc::alloc`
  47 /// method must either ensure that conditions like this are met, or
  48 /// use specific allocators with looser requirements.)
  49 #[stable(feature = "alloc_layout", since = "1.28.0")]
  50 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
  51 pub struct Layout {
  52     // size of the requested block of memory, measured in bytes.
  53     size_: usize,
  54
  55     // alignment of the requested block of memory, measured in bytes.
  56     // we ensure that this is always a power-of-two, because API's
  57     // like `posix_memalign` require it and it is a reasonable
  58     // constraint to impose on Layout constructors.
  59     //
  60     // (However, we do not analogously require `align >= sizeof(void*)`,
  61     //  even though that is *also* a requirement of `posix_memalign`.)
  62     align_: NonZeroUsize,
  63 }
  64
  65 impl Layout {
  66     /// Constructs a `Layout` from a given `size` and `align`,
  67     /// or returns `LayoutErr` if either of the following conditions
  68     /// are not met:
  69     ///
  70     /// * `align` must be a power of two,
  71     ///
  72     /// * `size`, when rounded up to the nearest multiple of `align`,
  73     ///    must not overflow (i.e. the rounded value must be less than
  74     ///    `usize::MAX`).
  75     #[stable(feature = "alloc_layout", since = "1.28.0")]
  76     #[inline]
  77     pub fn from_size_align(size: usize, align: usize) -> Result<Self, LayoutErr> {
  78         if !align.is_power_of_two() {
  79             return Err(LayoutErr { private: () });
  80         }
  81
  82         // (power-of-two implies align != 0.)
  83
  84         // Rounded up size is:
  85         //   size_rounded_up = (size + align - 1) & !(align - 1);
  86         //
  87         // We know from above that align != 0. If adding (align - 1)
  88         // does not overflow, then rounding up will be fine.
  89         //
  90         // Conversely, &-masking with !(align - 1) will subtract off
  91         // only low-order-bits. Thus if overflow occurs with the sum,
  92         // the &-mask cannot subtract enough to undo that overflow.
  93         //
  94         // Above implies that checking for summation overflow is both
  95         // necessary and sufficient.
  96         if size > usize::MAX - (align - 1) {
  97             return Err(LayoutErr { private: () });
  98         }
  99
 100         unsafe {
 101             Ok(Layout::from_size_align_unchecked(size, align))
 102         }
 103     }
 104
 105     /// Creates a layout, bypassing all checks.
 106     ///
 107     /// # Safety
 108     ///
 109     /// This function is unsafe as it does not verify the preconditions from
 110     /// [`Layout::from_size_align`](#method.from_size_align).
 111     #[stable(feature = "alloc_layout", since = "1.28.0")]
 112     #[inline]
 113     pub unsafe fn from_size_align_unchecked(size: usize, align: usize) -> Self {
 114         Layout { size_: size, align_: NonZeroUsize::new_unchecked(align) }
 115     }
 116
 117     /// The minimum size in bytes for a memory block of this layout.
 118     #[stable(feature = "alloc_layout", since = "1.28.0")]
 119     #[inline]
 120     pub fn size(&self) -> usize { self.size_ }
 121
 122     /// The minimum byte alignment for a memory block of this layout.
 123     #[stable(feature = "alloc_layout", since = "1.28.0")]
 124     #[inline]
 125     pub fn align(&self) -> usize { self.align_.get() }
 126
 127     /// Constructs a `Layout` suitable for holding a value of type `T`.
 128     #[stable(feature = "alloc_layout", since = "1.28.0")]
 129     #[inline]
 130     pub fn new<T>() -> Self {
 131         let (size, align) = size_align::<T>();
 132         // Note that the align is guaranteed by rustc to be a power of two and
 133         // the size+align combo is guaranteed to fit in our address space. As a
 134         // result use the unchecked constructor here to avoid inserting code
 135         // that panics if it isn't optimized well enough.
 136         debug_assert!(Layout::from_size_align(size, align).is_ok());
 137         unsafe {
 138             Layout::from_size_align_unchecked(size, align)
 139         }
 140     }
 141
 142     /// Produces layout describing a record that could be used to
 143     /// allocate backing structure for `T` (which could be a trait
 144     /// or other unsized type like a slice).
 145     #[stable(feature = "alloc_layout", since = "1.28.0")]
 146     #[inline]
 147     pub fn for_value<T: ?Sized>(t: &T) -> Self {
 148         let (size, align) = (mem::size_of_val(t), mem::align_of_val(t));
 149         // See rationale in `new` for why this us using an unsafe variant below
 150         debug_assert!(Layout::from_size_align(size, align).is_ok());
 151         unsafe {
 152             Layout::from_size_align_unchecked(size, align)
 153         }
 154     }
 155
 156     /// Creates a layout describing the record that can hold a value
 157     /// of the same layout as `self`, but that also is aligned to
 158     /// alignment `align` (measured in bytes).
 159     ///
 160     /// If `self` already meets the prescribed alignment, then returns
 161     /// `self`.
 162     ///
 163     /// Note that this method does not add any padding to the overall
 164     /// size, regardless of whether the returned layout has a different
 165     /// alignment. In other words, if `K` has size 16, `K.align_to(32)`
 166     /// will *still* have size 16.
 167     ///
 168     /// # Panics
 169     ///
 170     /// Panics if the combination of `self.size()` and the given `align`
 171     /// violates the conditions listed in
 172     /// [`Layout::from_size_align`](#method.from_size_align).
 173     #[unstable(feature = "allocator_api", issue = "32838")]
 174     #[inline]
 175     pub fn align_to(&self, align: usize) -> Self {
 176         Layout::from_size_align(self.size(), cmp::max(self.align(), align)).unwrap()
 177     }
 178
 179     /// Returns the amount of padding we must insert after `self`
 180     /// to ensure that the following address will satisfy `align`
 181     /// (measured in bytes).
 182     ///
 183     /// E.g. if `self.size()` is 9, then `self.padding_needed_for(4)`
 184     /// returns 3, because that is the minimum number of bytes of
 185     /// padding required to get a 4-aligned address (assuming that the
 186     /// corresponding memory block starts at a 4-aligned address).
 187     ///
 188     /// The return value of this function has no meaning if `align` is
 189     /// not a power-of-two.
 190     ///
 191     /// Note that the utility of the returned value requires `align`
 192     /// to be less than or equal to the alignment of the starting
 193     /// address for the whole allocated block of memory. One way to
 194     /// satisfy this constraint is to ensure `align <= self.align()`.
 195     #[unstable(feature = "allocator_api", issue = "32838")]
 196     #[inline]
 197     pub fn padding_needed_for(&self, align: usize) -> usize {
 198         let len = self.size();
 199
 200         // Rounded up value is:
 201         //   len_rounded_up = (len + align - 1) & !(align - 1);
 202         // and then we return the padding difference: `len_rounded_up - len`.
 203         //
 204         // We use modular arithmetic throughout:
 205         //
 206         // 1. align is guaranteed to be > 0, so align - 1 is always
 207         //    valid.
 208         //
 209         // 2. `len + align - 1` can overflow by at most `align - 1`,
 210         //    so the &-mask wth `!(align - 1)` will ensure that in the
 211         //    case of overflow, `len_rounded_up` will itself be 0.
 212         //    Thus the returned padding, when added to `len`, yields 0,
 213         //    which trivially satisfies the alignment `align`.
 214         //
 215         // (Of course, attempts to allocate blocks of memory whose
 216         // size and padding overflow in the above manner should cause
 217         // the allocator to yield an error anyway.)
 218
 219         let len_rounded_up = len.wrapping_add(align).wrapping_sub(1)
 220             & !align.wrapping_sub(1);
 221         return len_rounded_up.wrapping_sub(len);
 222     }
 223
 224     /// Creates a layout describing the record for `n` instances of
 225     /// `self`, with a suitable amount of padding between each to
 226     /// ensure that each instance is given its requested size and
 227     /// alignment. On success, returns `(k, offs)` where `k` is the
 228     /// layout of the array and `offs` is the distance between the start
 229     /// of each element in the array.
 230     ///
 231     /// On arithmetic overflow, returns `LayoutErr`.
 232     #[unstable(feature = "allocator_api", issue = "32838")]
 233     #[inline]
 234     pub fn repeat(&self, n: usize) -> Result<(Self, usize), LayoutErr> {
 235         let padded_size = self.size().checked_add(self.padding_needed_for(self.align()))
 236             .ok_or(LayoutErr { private: () })?;
 237         let alloc_size = padded_size.checked_mul(n)
 238             .ok_or(LayoutErr { private: () })?;
 239
 240         unsafe {
 241             // self.align is already known to be valid and alloc_size has been
 242             // padded already.
 243             Ok((Layout::from_size_align_unchecked(alloc_size, self.align()), padded_size))
 244         }
 245     }
 246
 247     /// Creates a layout describing the record for `self` followed by
 248     /// `next`, including any necessary padding to ensure that `next`
 249     /// will be properly aligned. Note that the result layout will
 250     /// satisfy the alignment properties of both `self` and `next`.
 251     ///
 252     /// Returns `Some((k, offset))`, where `k` is layout of the concatenated
 253     /// record and `offset` is the relative location, in bytes, of the
 254     /// start of the `next` embedded within the concatenated record
 255     /// (assuming that the record itself starts at offset 0).
 256     ///
 257     /// On arithmetic overflow, returns `LayoutErr`.
 258     #[unstable(feature = "allocator_api", issue = "32838")]
 259     #[inline]
 260     pub fn extend(&self, next: Self) -> Result<(Self, usize), LayoutErr> {
 261         let new_align = cmp::max(self.align(), next.align());
 262         let pad = self.padding_needed_for(next.align());
 263
 264         let offset = self.size().checked_add(pad)
 265             .ok_or(LayoutErr { private: () })?;
 266         let new_size = offset.checked_add(next.size())
 267             .ok_or(LayoutErr { private: () })?;
 268
 269         let layout = Layout::from_size_align(new_size, new_align)?;
 270         Ok((layout, offset))
 271     }
 272
 273     /// Creates a layout describing the record for `n` instances of
 274     /// `self`, with no padding between each instance.
 275     ///
 276     /// Note that, unlike `repeat`, `repeat_packed` does not guarantee
 277     /// that the repeated instances of `self` will be properly
 278     /// aligned, even if a given instance of `self` is properly
 279     /// aligned. In other words, if the layout returned by
 280     /// `repeat_packed` is used to allocate an array, it is not
 281     /// guaranteed that all elements in the array will be properly
 282     /// aligned.
 283     ///
 284     /// On arithmetic overflow, returns `LayoutErr`.
 285     #[unstable(feature = "allocator_api", issue = "32838")]
 286     #[inline]
 287     pub fn repeat_packed(&self, n: usize) -> Result<Self, LayoutErr> {
 288         let size = self.size().checked_mul(n).ok_or(LayoutErr { private: () })?;
 289         Layout::from_size_align(size, self.align())
 290     }
 291
 292     /// Creates a layout describing the record for `self` followed by
 293     /// `next` with no additional padding between the two. Since no
 294     /// padding is inserted, the alignment of `next` is irrelevant,
 295     /// and is not incorporated *at all* into the resulting layout.
 296     ///
 297     /// Returns `(k, offset)`, where `k` is layout of the concatenated
 298     /// record and `offset` is the relative location, in bytes, of the
 299     /// start of the `next` embedded within the concatenated record
 300     /// (assuming that the record itself starts at offset 0).
 301     ///
 302     /// (The `offset` is always the same as `self.size()`; we use this
 303     ///  signature out of convenience in matching the signature of
 304     ///  `extend`.)
 305     ///
 306     /// On arithmetic overflow, returns `LayoutErr`.
 307     #[unstable(feature = "allocator_api", issue = "32838")]
 308     #[inline]
 309     pub fn extend_packed(&self, next: Self) -> Result<(Self, usize), LayoutErr> {
 310         let new_size = self.size().checked_add(next.size())
 311             .ok_or(LayoutErr { private: () })?;
 312         let layout = Layout::from_size_align(new_size, self.align())?;
 313         Ok((layout, self.size()))
 314     }
 315
 316     /// Creates a layout describing the record for a `[T; n]`.
 317     ///
 318     /// On arithmetic overflow, returns `LayoutErr`.
 319     #[unstable(feature = "allocator_api", issue = "32838")]
 320     #[inline]
 321     pub fn array<T>(n: usize) -> Result<Self, LayoutErr> {
 322         Layout::new::<T>()
 323             .repeat(n)
 324             .map(|(k, offs)| {
 325                 debug_assert!(offs == mem::size_of::<T>());
 326                 k
 327             })
 328     }
 329 }
 330
 331 /// The parameters given to `Layout::from_size_align`
 332 /// or some other `Layout` constructor
 333 /// do not satisfy its documented constraints.
 334 #[stable(feature = "alloc_layout", since = "1.28.0")]
 335 #[derive(Clone, PartialEq, Eq, Debug)]
 336 pub struct LayoutErr {
 337     private: ()
 338 }
 339
 340 // (we need this for downstream impl of trait Error)
 341 #[stable(feature = "alloc_layout", since = "1.28.0")]
 342 impl fmt::Display for LayoutErr {
 343     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 344         f.write_str("invalid parameters to Layout::from_size_align")
 345     }
 346 }
 347
 348 /// The `AllocErr` error indicates an allocation failure
 349 /// that may be due to resource exhaustion or to
 350 /// something wrong when combining the given input arguments with this
 351 /// allocator.
 352 #[unstable(feature = "allocator_api", issue = "32838")]
 353 #[derive(Clone, PartialEq, Eq, Debug)]
 354 pub struct AllocErr;
 355
 356 // (we need this for downstream impl of trait Error)
 357 #[unstable(feature = "allocator_api", issue = "32838")]
 358 impl fmt::Display for AllocErr {
 359     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 360         f.write_str("memory allocation failed")
 361     }
 362 }
 363
 364 /// The `CannotReallocInPlace` error is used when `grow_in_place` or
 365 /// `shrink_in_place` were unable to reuse the given memory block for
 366 /// a requested layout.
 367 #[unstable(feature = "allocator_api", issue = "32838")]
 368 #[derive(Clone, PartialEq, Eq, Debug)]
 369 pub struct CannotReallocInPlace;
 370
 371 #[unstable(feature = "allocator_api", issue = "32838")]
 372 impl CannotReallocInPlace {
 373     pub fn description(&self) -> &str {
 374         "cannot reallocate allocator's memory in place"
 375     }
 376 }
 377
 378 // (we need this for downstream impl of trait Error)
 379 #[unstable(feature = "allocator_api", issue = "32838")]
 380 impl fmt::Display for CannotReallocInPlace {
 381     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 382         write!(f, "{}", self.description())
 383     }
 384 }
 385
 386 /// Augments `AllocErr` with a CapacityOverflow variant.
 387 // FIXME: should this be in libcore or liballoc?
 388 #[derive(Clone, PartialEq, Eq, Debug)]
 389 #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
 390 pub enum CollectionAllocErr {
 391     /// Error due to the computed capacity exceeding the collection's maximum
 392     /// (usually `isize::MAX` bytes).
 393     CapacityOverflow,
 394     /// Error due to the allocator (see the `AllocErr` type's docs).
 395     AllocErr,
 396 }
 397
 398 #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
 399 impl From<AllocErr> for CollectionAllocErr {
 400     #[inline]
 401     fn from(AllocErr: AllocErr) -> Self {
 402         CollectionAllocErr::AllocErr
 403     }
 404 }
 405
 406 #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
 407 impl From<LayoutErr> for CollectionAllocErr {
 408     #[inline]
 409     fn from(_: LayoutErr) -> Self {
 410         CollectionAllocErr::CapacityOverflow
 411     }
 412 }
 413
 414 /// A memory allocator that can be registered as the standard library’s default
 415 /// though the `#[global_allocator]` attributes.
 416 ///
 417 /// Some of the methods require that a memory block be *currently
 418 /// allocated* via an allocator. This means that:
 419 ///
 420 /// * the starting address for that memory block was previously
 421 ///   returned by a previous call to an allocation method
 422 ///   such as `alloc`, and
 423 ///
 424 /// * the memory block has not been subsequently deallocated, where
 425 ///   blocks are deallocated either by being passed to a deallocation
 426 ///   method such as `dealloc` or by being
 427 ///   passed to a reallocation method that returns a non-null pointer.
 428 ///
 429 ///
 430 /// # Example
 431 ///
 432 /// ```no_run
 433 /// use std::alloc::{GlobalAlloc, Layout, alloc};
 434 /// use std::ptr::null_mut;
 435 ///
 436 /// struct MyAllocator;
 437 ///
 438 /// unsafe impl GlobalAlloc for MyAllocator {
 439 ///     unsafe fn alloc(&self, _layout: Layout) -> *mut u8 { null_mut() }
 440 ///     unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {}
 441 /// }
 442 ///
 443 /// #[global_allocator]
 444 /// static A: MyAllocator = MyAllocator;
 445 ///
 446 /// fn main() {
 447 ///     unsafe {
 448 ///         assert!(alloc(Layout::new::<u32>()).is_null())
 449 ///     }
 450 /// }
 451 /// ```
 452 ///
 453 /// # Unsafety
 454 ///
 455 /// The `GlobalAlloc` trait is an `unsafe` trait for a number of reasons, and
 456 /// implementors must ensure that they adhere to these contracts:
 457 ///
 458 /// * It's undefined behavior if global allocators unwind.  This restriction may
 459 ///   be lifted in the future, but currently a panic from any of these
 460 ///   functions may lead to memory unsafety.
 461 ///
 462 /// * `Layout` queries and calculations in general must be correct. Callers of
 463 ///   this trait are allowed to rely on the contracts defined on each method,
 464 ///   and implementors must ensure such contracts remain true.
 465 #[stable(feature = "global_alloc", since = "1.28.0")]
 466 pub unsafe trait GlobalAlloc {
 467     /// Allocate memory as described by the given `layout`.
 468     ///
 469     /// Returns a pointer to newly-allocated memory,
 470     /// or null to indicate allocation failure.
 471     ///
 472     /// # Safety
 473     ///
 474     /// This function is unsafe because undefined behavior can result
 475     /// if the caller does not ensure that `layout` has non-zero size.
 476     ///
 477     /// (Extension subtraits might provide more specific bounds on
 478     /// behavior, e.g. guarantee a sentinel address or a null pointer
 479     /// in response to a zero-size allocation request.)
 480     ///
 481     /// The allocated block of memory may or may not be initialized.
 482     ///
 483     /// # Errors
 484     ///
 485     /// Returning a null pointer indicates that either memory is exhausted
 486     /// or `layout` does not meet allocator's size or alignment constraints.
 487     ///
 488     /// Implementations are encouraged to return null on memory
 489     /// exhaustion rather than aborting, but this is not
 490     /// a strict requirement. (Specifically: it is *legal* to
 491     /// implement this trait atop an underlying native allocation
 492     /// library that aborts on memory exhaustion.)
 493     ///
 494     /// Clients wishing to abort computation in response to an
 495     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
 496     /// rather than directly invoking `panic!` or similar.
 497     ///
 498     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 499     #[stable(feature = "global_alloc", since = "1.28.0")]
 500     unsafe fn alloc(&self, layout: Layout) -> *mut u8;
 501
 502     /// Deallocate the block of memory at the given `ptr` pointer with the given `layout`.
 503     ///
 504     /// # Safety
 505     ///
 506     /// This function is unsafe because undefined behavior can result
 507     /// if the caller does not ensure all of the following:
 508     ///
 509     /// * `ptr` must denote a block of memory currently allocated via
 510     ///   this allocator,
 511     ///
 512     /// * `layout` must be the same layout that was used
 513     ///   to allocated that block of memory,
 514     #[stable(feature = "global_alloc", since = "1.28.0")]
 515     unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
 516
 517     /// Behaves like `alloc`, but also ensures that the contents
 518     /// are set to zero before being returned.
 519     ///
 520     /// # Safety
 521     ///
 522     /// This function is unsafe for the same reasons that `alloc` is.
 523     /// However the allocated block of memory is guaranteed to be initialized.
 524     ///
 525     /// # Errors
 526     ///
 527     /// Returning a null pointer indicates that either memory is exhausted
 528     /// or `layout` does not meet allocator's size or alignment constraints,
 529     /// just as in `alloc`.
 530     ///
 531     /// Clients wishing to abort computation in response to an
 532     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
 533     /// rather than directly invoking `panic!` or similar.
 534     ///
 535     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 536     #[stable(feature = "global_alloc", since = "1.28.0")]
 537     unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
 538         let size = layout.size();
 539         let ptr = self.alloc(layout);
 540         if !ptr.is_null() {
 541             ptr::write_bytes(ptr, 0, size);
 542         }
 543         ptr
 544     }
 545
 546     /// Shink or grow a block of memory to the given `new_size`.
 547     /// The block is described by the given `ptr` pointer and `layout`.
 548     ///
 549     /// If this returns a non-null pointer, then ownership of the memory block
 550     /// referenced by `ptr` has been transferred to this alloctor.
 551     /// The memory may or may not have been deallocated,
 552     /// and should be considered unusable (unless of course it was
 553     /// transferred back to the caller again via the return value of
 554     /// this method).
 555     ///
 556     /// If this method returns null, then ownership of the memory
 557     /// block has not been transferred to this allocator, and the
 558     /// contents of the memory block are unaltered.
 559     ///
 560     /// # Safety
 561     ///
 562     /// This function is unsafe because undefined behavior can result
 563     /// if the caller does not ensure all of the following:
 564     ///
 565     /// * `ptr` must be currently allocated via this allocator,
 566     ///
 567     /// * `layout` must be the same layout that was used
 568     ///   to allocated that block of memory,
 569     ///
 570     /// * `new_size` must be greater than zero.
 571     ///
 572     /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`,
 573     ///   must not overflow (i.e. the rounded value must be less than `usize::MAX`).
 574     ///
 575     /// (Extension subtraits might provide more specific bounds on
 576     /// behavior, e.g. guarantee a sentinel address or a null pointer
 577     /// in response to a zero-size allocation request.)
 578     ///
 579     /// # Errors
 580     ///
 581     /// Returns null if the new layout does not meet the size
 582     /// and alignment constraints of the allocator, or if reallocation
 583     /// otherwise fails.
 584     ///
 585     /// Implementations are encouraged to return null on memory
 586     /// exhaustion rather than panicking or aborting, but this is not
 587     /// a strict requirement. (Specifically: it is *legal* to
 588     /// implement this trait atop an underlying native allocation
 589     /// library that aborts on memory exhaustion.)
 590     ///
 591     /// Clients wishing to abort computation in response to a
 592     /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
 593     /// rather than directly invoking `panic!` or similar.
 594     ///
 595     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 596     #[stable(feature = "global_alloc", since = "1.28.0")]
 597     unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
 598         let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
 599         let new_ptr = self.alloc(new_layout);
 600         if !new_ptr.is_null() {
 601             ptr::copy_nonoverlapping(
 602                 ptr,
 603                 new_ptr,
 604                 cmp::min(layout.size(), new_size),
 605             );
 606             self.dealloc(ptr, layout);
 607         }
 608         new_ptr
 609     }
 610 }
 611
 612 /// An implementation of `Alloc` can allocate, reallocate, and
 613 /// deallocate arbitrary blocks of data described via `Layout`.
 614 ///
 615 /// Some of the methods require that a memory block be *currently
 616 /// allocated* via an allocator. This means that:
 617 ///
 618 /// * the starting address for that memory block was previously
 619 ///   returned by a previous call to an allocation method (`alloc`,
 620 ///   `alloc_zeroed`, `alloc_excess`, `alloc_one`, `alloc_array`) or
 621 ///   reallocation method (`realloc`, `realloc_excess`, or
 622 ///   `realloc_array`), and
 623 ///
 624 /// * the memory block has not been subsequently deallocated, where
 625 ///   blocks are deallocated either by being passed to a deallocation
 626 ///   method (`dealloc`, `dealloc_one`, `dealloc_array`) or by being
 627 ///   passed to a reallocation method (see above) that returns `Ok`.
 628 ///
 629 /// A note regarding zero-sized types and zero-sized layouts: many
 630 /// methods in the `Alloc` trait state that allocation requests
 631 /// must be non-zero size, or else undefined behavior can result.
 632 ///
 633 /// * However, some higher-level allocation methods (`alloc_one`,
 634 ///   `alloc_array`) are well-defined on zero-sized types and can
 635 ///   optionally support them: it is left up to the implementor
 636 ///   whether to return `Err`, or to return `Ok` with some pointer.
 637 ///
 638 /// * If an `Alloc` implementation chooses to return `Ok` in this
 639 ///   case (i.e. the pointer denotes a zero-sized inaccessible block)
 640 ///   then that returned pointer must be considered "currently
 641 ///   allocated". On such an allocator, *all* methods that take
 642 ///   currently-allocated pointers as inputs must accept these
 643 ///   zero-sized pointers, *without* causing undefined behavior.
 644 ///
 645 /// * In other words, if a zero-sized pointer can flow out of an
 646 ///   allocator, then that allocator must likewise accept that pointer
 647 ///   flowing back into its deallocation and reallocation methods.
 648 ///
 649 /// Some of the methods require that a layout *fit* a memory block.
 650 /// What it means for a layout to "fit" a memory block means (or
 651 /// equivalently, for a memory block to "fit" a layout) is that the
 652 /// following two conditions must hold:
 653 ///
 654 /// 1. The block's starting address must be aligned to `layout.align()`.
 655 ///
 656 /// 2. The block's size must fall in the range `[use_min, use_max]`, where:
 657 ///
 658 ///    * `use_min` is `self.usable_size(layout).0`, and
 659 ///
 660 ///    * `use_max` is the capacity that was (or would have been)
 661 ///      returned when (if) the block was allocated via a call to
 662 ///      `alloc_excess` or `realloc_excess`.
 663 ///
 664 /// Note that:
 665 ///
 666 ///  * the size of the layout most recently used to allocate the block
 667 ///    is guaranteed to be in the range `[use_min, use_max]`, and
 668 ///
 669 ///  * a lower-bound on `use_max` can be safely approximated by a call to
 670 ///    `usable_size`.
 671 ///
 672 ///  * if a layout `k` fits a memory block (denoted by `ptr`)
 673 ///    currently allocated via an allocator `a`, then it is legal to
 674 ///    use that layout to deallocate it, i.e. `a.dealloc(ptr, k);`.
 675 ///
 676 /// # Unsafety
 677 ///
 678 /// The `Alloc` trait is an `unsafe` trait for a number of reasons, and
 679 /// implementors must ensure that they adhere to these contracts:
 680 ///
 681 /// * Pointers returned from allocation functions must point to valid memory and
 682 ///   retain their validity until at least the instance of `Alloc` is dropped
 683 ///   itself.
 684 ///
 685 /// * `Layout` queries and calculations in general must be correct. Callers of
 686 ///   this trait are allowed to rely on the contracts defined on each method,
 687 ///   and implementors must ensure such contracts remain true.
 688 ///
 689 /// Note that this list may get tweaked over time as clarifications are made in
 690 /// the future.
 691 #[unstable(feature = "allocator_api", issue = "32838")]
 692 pub unsafe trait Alloc {
 693
 694     // (Note: some existing allocators have unspecified but well-defined
 695     // behavior in response to a zero size allocation request ;
 696     // e.g. in C, `malloc` of 0 will either return a null pointer or a
 697     // unique pointer, but will not have arbitrary undefined
 698     // behavior.
 699     // However in jemalloc for example,
 700     // `mallocx(0)` is documented as undefined behavior.)
 701
 702     /// Returns a pointer meeting the size and alignment guarantees of
 703     /// `layout`.
 704     ///
 705     /// If this method returns an `Ok(addr)`, then the `addr` returned
 706     /// will be non-null address pointing to a block of storage
 707     /// suitable for holding an instance of `layout`.
 708     ///
 709     /// The returned block of storage may or may not have its contents
 710     /// initialized. (Extension subtraits might restrict this
 711     /// behavior, e.g. to ensure initialization to particular sets of
 712     /// bit patterns.)
 713     ///
 714     /// # Safety
 715     ///
 716     /// This function is unsafe because undefined behavior can result
 717     /// if the caller does not ensure that `layout` has non-zero size.
 718     ///
 719     /// (Extension subtraits might provide more specific bounds on
 720     /// behavior, e.g. guarantee a sentinel address or a null pointer
 721     /// in response to a zero-size allocation request.)
 722     ///
 723     /// # Errors
 724     ///
 725     /// Returning `Err` indicates that either memory is exhausted or
 726     /// `layout` does not meet allocator's size or alignment
 727     /// constraints.
 728     ///
 729     /// Implementations are encouraged to return `Err` on memory
 730     /// exhaustion rather than panicking or aborting, but this is not
 731     /// a strict requirement. (Specifically: it is *legal* to
 732     /// implement this trait atop an underlying native allocation
 733     /// library that aborts on memory exhaustion.)
 734     ///
 735     /// Clients wishing to abort computation in response to an
 736     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
 737     /// rather than directly invoking `panic!` or similar.
 738     ///
 739     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 740     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr>;
 741
 742     /// Deallocate the memory referenced by `ptr`.
 743     ///
 744     /// # Safety
 745     ///
 746     /// This function is unsafe because undefined behavior can result
 747     /// if the caller does not ensure all of the following:
 748     ///
 749     /// * `ptr` must denote a block of memory currently allocated via
 750     ///   this allocator,
 751     ///
 752     /// * `layout` must *fit* that block of memory,
 753     ///
 754     /// * In addition to fitting the block of memory `layout`, the
 755     ///   alignment of the `layout` must match the alignment used
 756     ///   to allocate that block of memory.
 757     unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
 758
 759     // == ALLOCATOR-SPECIFIC QUANTITIES AND LIMITS ==
 760     // usable_size
 761
 762     /// Returns bounds on the guaranteed usable size of a successful
 763     /// allocation created with the specified `layout`.
 764     ///
 765     /// In particular, if one has a memory block allocated via a given
 766     /// allocator `a` and layout `k` where `a.usable_size(k)` returns
 767     /// `(l, u)`, then one can pass that block to `a.dealloc()` with a
 768     /// layout in the size range [l, u].
 769     ///
 770     /// (All implementors of `usable_size` must ensure that
 771     /// `l <= k.size() <= u`)
 772     ///
 773     /// Both the lower- and upper-bounds (`l` and `u` respectively)
 774     /// are provided, because an allocator based on size classes could
 775     /// misbehave if one attempts to deallocate a block without
 776     /// providing a correct value for its size (i.e., one within the
 777     /// range `[l, u]`).
 778     ///
 779     /// Clients who wish to make use of excess capacity are encouraged
 780     /// to use the `alloc_excess` and `realloc_excess` instead, as
 781     /// this method is constrained to report conservative values that
 782     /// serve as valid bounds for *all possible* allocation method
 783     /// calls.
 784     ///
 785     /// However, for clients that do not wish to track the capacity
 786     /// returned by `alloc_excess` locally, this method is likely to
 787     /// produce useful results.
 788     #[inline]
 789     fn usable_size(&self, layout: &Layout) -> (usize, usize) {
 790         (layout.size(), layout.size())
 791     }
 792
 793     // == METHODS FOR MEMORY REUSE ==
 794     // realloc. alloc_excess, realloc_excess
 795
 796     /// Returns a pointer suitable for holding data described by
 797     /// a new layout with `layout`’s alginment and a size given
 798     /// by `new_size`. To
 799     /// accomplish this, this may extend or shrink the allocation
 800     /// referenced by `ptr` to fit the new layout.
 801     ///
 802     /// If this returns `Ok`, then ownership of the memory block
 803     /// referenced by `ptr` has been transferred to this
 804     /// allocator. The memory may or may not have been freed, and
 805     /// should be considered unusable (unless of course it was
 806     /// transferred back to the caller again via the return value of
 807     /// this method).
 808     ///
 809     /// If this method returns `Err`, then ownership of the memory
 810     /// block has not been transferred to this allocator, and the
 811     /// contents of the memory block are unaltered.
 812     ///
 813     /// # Safety
 814     ///
 815     /// This function is unsafe because undefined behavior can result
 816     /// if the caller does not ensure all of the following:
 817     ///
 818     /// * `ptr` must be currently allocated via this allocator,
 819     ///
 820     /// * `layout` must *fit* the `ptr` (see above). (The `new_size`
 821     ///   argument need not fit it.)
 822     ///
 823     /// * `new_size` must be greater than zero.
 824     ///
 825     /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`,
 826     ///   must not overflow (i.e. the rounded value must be less than `usize::MAX`).
 827     ///
 828     /// (Extension subtraits might provide more specific bounds on
 829     /// behavior, e.g. guarantee a sentinel address or a null pointer
 830     /// in response to a zero-size allocation request.)
 831     ///
 832     /// # Errors
 833     ///
 834     /// Returns `Err` only if the new layout
 835     /// does not meet the allocator's size
 836     /// and alignment constraints of the allocator, or if reallocation
 837     /// otherwise fails.
 838     ///
 839     /// Implementations are encouraged to return `Err` on memory
 840     /// exhaustion rather than panicking or aborting, but this is not
 841     /// a strict requirement. (Specifically: it is *legal* to
 842     /// implement this trait atop an underlying native allocation
 843     /// library that aborts on memory exhaustion.)
 844     ///
 845     /// Clients wishing to abort computation in response to a
 846     /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
 847     /// rather than directly invoking `panic!` or similar.
 848     ///
 849     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 850     unsafe fn realloc(&mut self,
 851                       ptr: NonNull<u8>,
 852                       layout: Layout,
 853                       new_size: usize) -> Result<NonNull<u8>, AllocErr> {
 854         let old_size = layout.size();
 855
 856         if new_size >= old_size {
 857             if let Ok(()) = self.grow_in_place(ptr, layout.clone(), new_size) {
 858                 return Ok(ptr);
 859             }
 860         } else if new_size < old_size {
 861             if let Ok(()) = self.shrink_in_place(ptr, layout.clone(), new_size) {
 862                 return Ok(ptr);
 863             }
 864         }
 865
 866         // otherwise, fall back on alloc + copy + dealloc.
 867         let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
 868         let result = self.alloc(new_layout);
 869         if let Ok(new_ptr) = result {
 870             ptr::copy_nonoverlapping(ptr.as_ptr(),
 871                                      new_ptr.as_ptr(),
 872                                      cmp::min(old_size, new_size));
 873             self.dealloc(ptr, layout);
 874         }
 875         result
 876     }
 877
 878     /// Behaves like `alloc`, but also ensures that the contents
 879     /// are set to zero before being returned.
 880     ///
 881     /// # Safety
 882     ///
 883     /// This function is unsafe for the same reasons that `alloc` is.
 884     ///
 885     /// # Errors
 886     ///
 887     /// Returning `Err` indicates that either memory is exhausted or
 888     /// `layout` does not meet allocator's size or alignment
 889     /// constraints, just as in `alloc`.
 890     ///
 891     /// Clients wishing to abort computation in response to an
 892     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
 893     /// rather than directly invoking `panic!` or similar.
 894     ///
 895     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 896     unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
 897         let size = layout.size();
 898         let p = self.alloc(layout);
 899         if let Ok(p) = p {
 900             ptr::write_bytes(p.as_ptr(), 0, size);
 901         }
 902         p
 903     }
 904
 905     /// Behaves like `alloc`, but also returns the whole size of
 906     /// the returned block. For some `layout` inputs, like arrays, this
 907     /// may include extra storage usable for additional data.
 908     ///
 909     /// # Safety
 910     ///
 911     /// This function is unsafe for the same reasons that `alloc` is.
 912     ///
 913     /// # Errors
 914     ///
 915     /// Returning `Err` indicates that either memory is exhausted or
 916     /// `layout` does not meet allocator's size or alignment
 917     /// constraints, just as in `alloc`.
 918     ///
 919     /// Clients wishing to abort computation in response to an
 920     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
 921     /// rather than directly invoking `panic!` or similar.
 922     ///
 923     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 924     unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr> {
 925         let usable_size = self.usable_size(&layout);
 926         self.alloc(layout).map(|p| Excess(p, usable_size.1))
 927     }
 928
 929     /// Behaves like `realloc`, but also returns the whole size of
 930     /// the returned block. For some `layout` inputs, like arrays, this
 931     /// may include extra storage usable for additional data.
 932     ///
 933     /// # Safety
 934     ///
 935     /// This function is unsafe for the same reasons that `realloc` is.
 936     ///
 937     /// # Errors
 938     ///
 939     /// Returning `Err` indicates that either memory is exhausted or
 940     /// `layout` does not meet allocator's size or alignment
 941     /// constraints, just as in `realloc`.
 942     ///
 943     /// Clients wishing to abort computation in response to a
 944     /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
 945     /// rather than directly invoking `panic!` or similar.
 946     ///
 947     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 948     unsafe fn realloc_excess(&mut self,
 949                              ptr: NonNull<u8>,
 950                              layout: Layout,
 951                              new_size: usize) -> Result<Excess, AllocErr> {
 952         let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
 953         let usable_size = self.usable_size(&new_layout);
 954         self.realloc(ptr, layout, new_size)
 955             .map(|p| Excess(p, usable_size.1))
 956     }
 957
 958     /// Attempts to extend the allocation referenced by `ptr` to fit `new_size`.
 959     ///
 960     /// If this returns `Ok`, then the allocator has asserted that the
 961     /// memory block referenced by `ptr` now fits `new_size`, and thus can
 962     /// be used to carry data of a layout of that size and same alignment as
 963     /// `layout`. (The allocator is allowed to
 964     /// expend effort to accomplish this, such as extending the memory block to
 965     /// include successor blocks, or virtual memory tricks.)
 966     ///
 967     /// Regardless of what this method returns, ownership of the
 968     /// memory block referenced by `ptr` has not been transferred, and
 969     /// the contents of the memory block are unaltered.
 970     ///
 971     /// # Safety
 972     ///
 973     /// This function is unsafe because undefined behavior can result
 974     /// if the caller does not ensure all of the following:
 975     ///
 976     /// * `ptr` must be currently allocated via this allocator,
 977     ///
 978     /// * `layout` must *fit* the `ptr` (see above); note the
 979     ///   `new_size` argument need not fit it,
 980     ///
 981     /// * `new_size` must not be less than `layout.size()`,
 982     ///
 983     /// # Errors
 984     ///
 985     /// Returns `Err(CannotReallocInPlace)` when the allocator is
 986     /// unable to assert that the memory block referenced by `ptr`
 987     /// could fit `layout`.
 988     ///
 989     /// Note that one cannot pass `CannotReallocInPlace` to the `handle_alloc_error`
 990     /// function; clients are expected either to be able to recover from
 991     /// `grow_in_place` failures without aborting, or to fall back on
 992     /// another reallocation method before resorting to an abort.
 993     unsafe fn grow_in_place(&mut self,
 994                             ptr: NonNull<u8>,
 995                             layout: Layout,
 996                             new_size: usize) -> Result<(), CannotReallocInPlace> {
 997         let _ = ptr; // this default implementation doesn't care about the actual address.
 998         debug_assert!(new_size >= layout.size());
 999         let (_l, u) = self.usable_size(&layout);
1000         // _l <= layout.size()                       [guaranteed by usable_size()]
1001         //       layout.size() <= new_layout.size()  [required by this method]
1002         if new_size <= u {
1003             return Ok(());
1004         } else {
1005             return Err(CannotReallocInPlace);
1006         }
1007     }
1008
1009     /// Attempts to shrink the allocation referenced by `ptr` to fit `new_size`.
1010     ///
1011     /// If this returns `Ok`, then the allocator has asserted that the
1012     /// memory block referenced by `ptr` now fits `new_size`, and
1013     /// thus can only be used to carry data of that smaller
1014     /// layout. (The allocator is allowed to take advantage of this,
1015     /// carving off portions of the block for reuse elsewhere.) The
1016     /// truncated contents of the block within the smaller layout are
1017     /// unaltered, and ownership of block has not been transferred.
1018     ///
1019     /// If this returns `Err`, then the memory block is considered to
1020     /// still represent the original (larger) `layout`. None of the
1021     /// block has been carved off for reuse elsewhere, ownership of
1022     /// the memory block has not been transferred, and the contents of
1023     /// the memory block are unaltered.
1024     ///
1025     /// # Safety
1026     ///
1027     /// This function is unsafe because undefined behavior can result
1028     /// if the caller does not ensure all of the following:
1029     ///
1030     /// * `ptr` must be currently allocated via this allocator,
1031     ///
1032     /// * `layout` must *fit* the `ptr` (see above); note the
1033     ///   `new_size` argument need not fit it,
1034     ///
1035     /// * `new_size` must not be greater than `layout.size()`
1036     ///   (and must be greater than zero),
1037     ///
1038     /// # Errors
1039     ///
1040     /// Returns `Err(CannotReallocInPlace)` when the allocator is
1041     /// unable to assert that the memory block referenced by `ptr`
1042     /// could fit `layout`.
1043     ///
1044     /// Note that one cannot pass `CannotReallocInPlace` to the `handle_alloc_error`
1045     /// function; clients are expected either to be able to recover from
1046     /// `shrink_in_place` failures without aborting, or to fall back
1047     /// on another reallocation method before resorting to an abort.
1048     unsafe fn shrink_in_place(&mut self,
1049                               ptr: NonNull<u8>,
1050                               layout: Layout,
1051                               new_size: usize) -> Result<(), CannotReallocInPlace> {
1052         let _ = ptr; // this default implementation doesn't care about the actual address.
1053         debug_assert!(new_size <= layout.size());
1054         let (l, _u) = self.usable_size(&layout);
1055         //                      layout.size() <= _u  [guaranteed by usable_size()]
1056         // new_layout.size() <= layout.size()        [required by this method]
1057         if l <= new_size {
1058             return Ok(());
1059         } else {
1060             return Err(CannotReallocInPlace);
1061         }
1062     }
1063
1064
1065     // == COMMON USAGE PATTERNS ==
1066     // alloc_one, dealloc_one, alloc_array, realloc_array. dealloc_array
1067
1068     /// Allocates a block suitable for holding an instance of `T`.
1069     ///
1070     /// Captures a common usage pattern for allocators.
1071     ///
1072     /// The returned block is suitable for passing to the
1073     /// `alloc`/`realloc` methods of this allocator.
1074     ///
1075     /// Note to implementors: If this returns `Ok(ptr)`, then `ptr`
1076     /// must be considered "currently allocated" and must be
1077     /// acceptable input to methods such as `realloc` or `dealloc`,
1078     /// *even if* `T` is a zero-sized type. In other words, if your
1079     /// `Alloc` implementation overrides this method in a manner
1080     /// that can return a zero-sized `ptr`, then all reallocation and
1081     /// deallocation methods need to be similarly overridden to accept
1082     /// such values as input.
1083     ///
1084     /// # Errors
1085     ///
1086     /// Returning `Err` indicates that either memory is exhausted or
1087     /// `T` does not meet allocator's size or alignment constraints.
1088     ///
1089     /// For zero-sized `T`, may return either of `Ok` or `Err`, but
1090     /// will *not* yield undefined behavior.
1091     ///
1092     /// Clients wishing to abort computation in response to an
1093     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
1094     /// rather than directly invoking `panic!` or similar.
1095     ///
1096     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1097     fn alloc_one<T>(&mut self) -> Result<NonNull<T>, AllocErr>
1098         where Self: Sized
1099     {
1100         let k = Layout::new::<T>();
1101         if k.size() > 0 {
1102             unsafe { self.alloc(k).map(|p| p.cast()) }
1103         } else {
1104             Err(AllocErr)
1105         }
1106     }
1107
1108     /// Deallocates a block suitable for holding an instance of `T`.
1109     ///
1110     /// The given block must have been produced by this allocator,
1111     /// and must be suitable for storing a `T` (in terms of alignment
1112     /// as well as minimum and maximum size); otherwise yields
1113     /// undefined behavior.
1114     ///
1115     /// Captures a common usage pattern for allocators.
1116     ///
1117     /// # Safety
1118     ///
1119     /// This function is unsafe because undefined behavior can result
1120     /// if the caller does not ensure both:
1121     ///
1122     /// * `ptr` must denote a block of memory currently allocated via this allocator
1123     ///
1124     /// * the layout of `T` must *fit* that block of memory.
1125     unsafe fn dealloc_one<T>(&mut self, ptr: NonNull<T>)
1126         where Self: Sized
1127     {
1128         let k = Layout::new::<T>();
1129         if k.size() > 0 {
1130             self.dealloc(ptr.cast(), k);
1131         }
1132     }
1133
1134     /// Allocates a block suitable for holding `n` instances of `T`.
1135     ///
1136     /// Captures a common usage pattern for allocators.
1137     ///
1138     /// The returned block is suitable for passing to the
1139     /// `alloc`/`realloc` methods of this allocator.
1140     ///
1141     /// Note to implementors: If this returns `Ok(ptr)`, then `ptr`
1142     /// must be considered "currently allocated" and must be
1143     /// acceptable input to methods such as `realloc` or `dealloc`,
1144     /// *even if* `T` is a zero-sized type. In other words, if your
1145     /// `Alloc` implementation overrides this method in a manner
1146     /// that can return a zero-sized `ptr`, then all reallocation and
1147     /// deallocation methods need to be similarly overridden to accept
1148     /// such values as input.
1149     ///
1150     /// # Errors
1151     ///
1152     /// Returning `Err` indicates that either memory is exhausted or
1153     /// `[T; n]` does not meet allocator's size or alignment
1154     /// constraints.
1155     ///
1156     /// For zero-sized `T` or `n == 0`, may return either of `Ok` or
1157     /// `Err`, but will *not* yield undefined behavior.
1158     ///
1159     /// Always returns `Err` on arithmetic overflow.
1160     ///
1161     /// Clients wishing to abort computation in response to an
1162     /// allocation error are encouraged to call the [`handle_alloc_error`] function,
1163     /// rather than directly invoking `panic!` or similar.
1164     ///
1165     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1166     fn alloc_array<T>(&mut self, n: usize) -> Result<NonNull<T>, AllocErr>
1167         where Self: Sized
1168     {
1169         match Layout::array::<T>(n) {
1170             Ok(ref layout) if layout.size() > 0 => {
1171                 unsafe {
1172                     self.alloc(layout.clone()).map(|p| p.cast())
1173                 }
1174             }
1175             _ => Err(AllocErr),
1176         }
1177     }
1178
1179     /// Reallocates a block previously suitable for holding `n_old`
1180     /// instances of `T`, returning a block suitable for holding
1181     /// `n_new` instances of `T`.
1182     ///
1183     /// Captures a common usage pattern for allocators.
1184     ///
1185     /// The returned block is suitable for passing to the
1186     /// `alloc`/`realloc` methods of this allocator.
1187     ///
1188     /// # Safety
1189     ///
1190     /// This function is unsafe because undefined behavior can result
1191     /// if the caller does not ensure all of the following:
1192     ///
1193     /// * `ptr` must be currently allocated via this allocator,
1194     ///
1195     /// * the layout of `[T; n_old]` must *fit* that block of memory.
1196     ///
1197     /// # Errors
1198     ///
1199     /// Returning `Err` indicates that either memory is exhausted or
1200     /// `[T; n_new]` does not meet allocator's size or alignment
1201     /// constraints.
1202     ///
1203     /// For zero-sized `T` or `n_new == 0`, may return either of `Ok` or
1204     /// `Err`, but will *not* yield undefined behavior.
1205     ///
1206     /// Always returns `Err` on arithmetic overflow.
1207     ///
1208     /// Clients wishing to abort computation in response to a
1209     /// reallocation error are encouraged to call the [`handle_alloc_error`] function,
1210     /// rather than directly invoking `panic!` or similar.
1211     ///
1212     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
1213     unsafe fn realloc_array<T>(&mut self,
1214                                ptr: NonNull<T>,
1215                                n_old: usize,
1216                                n_new: usize) -> Result<NonNull<T>, AllocErr>
1217         where Self: Sized
1218     {
1219         match (Layout::array::<T>(n_old), Layout::array::<T>(n_new)) {
1220             (Ok(ref k_old), Ok(ref k_new)) if k_old.size() > 0 && k_new.size() > 0 => {
1221                 debug_assert!(k_old.align() == k_new.align());
1222                 self.realloc(ptr.cast(), k_old.clone(), k_new.size()).map(NonNull::cast)
1223             }
1224             _ => {
1225                 Err(AllocErr)
1226             }
1227         }
1228     }
1229
1230     /// Deallocates a block suitable for holding `n` instances of `T`.
1231     ///
1232     /// Captures a common usage pattern for allocators.
1233     ///
1234     /// # Safety
1235     ///
1236     /// This function is unsafe because undefined behavior can result
1237     /// if the caller does not ensure both:
1238     ///
1239     /// * `ptr` must denote a block of memory currently allocated via this allocator
1240     ///
1241     /// * the layout of `[T; n]` must *fit* that block of memory.
1242     ///
1243     /// # Errors
1244     ///
1245     /// Returning `Err` indicates that either `[T; n]` or the given
1246     /// memory block does not meet allocator's size or alignment
1247     /// constraints.
1248     ///
1249     /// Always returns `Err` on arithmetic overflow.
1250     unsafe fn dealloc_array<T>(&mut self, ptr: NonNull<T>, n: usize) -> Result<(), AllocErr>
1251         where Self: Sized
1252     {
1253         match Layout::array::<T>(n) {
1254             Ok(ref k) if k.size() > 0 => {
1255                 Ok(self.dealloc(ptr.cast(), k.clone()))
1256             }
1257             _ => {
1258                 Err(AllocErr)
1259             }
1260         }
1261     }
1262 }