src/libcore/alloc.rs

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