src/libcore/alloc/mod.rs

   1 //! Memory allocation APIs
   2
   3 #![stable(feature = "alloc_module", since = "1.28.0")]
   4
   5 mod global;
   6 mod layout;
   7
   8 #[stable(feature = "global_alloc", since = "1.28.0")]
   9 pub use self::global::GlobalAlloc;
  10 #[stable(feature = "alloc_layout", since = "1.28.0")]
  11 pub use self::layout::{Layout, LayoutErr};
  12
  13 use crate::fmt;
  14 use crate::ptr::{self, NonNull};
  15
  16 /// The `AllocErr` error indicates an allocation failure
  17 /// that may be due to resource exhaustion or to
  18 /// something wrong when combining the given input arguments with this
  19 /// allocator.
  20 #[unstable(feature = "allocator_api", issue = "32838")]
  21 #[derive(Clone, PartialEq, Eq, Debug)]
  22 pub struct AllocErr;
  23
  24 // (we need this for downstream impl of trait Error)
  25 #[unstable(feature = "allocator_api", issue = "32838")]
  26 impl fmt::Display for AllocErr {
  27     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  28         f.write_str("memory allocation failed")
  29     }
  30 }
  31
  32 /// A desired initial state for allocated memory.
  33 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  34 #[unstable(feature = "allocator_api", issue = "32838")]
  35 pub enum AllocInit {
  36     /// The contents of the new memory are uninitialized.
  37     Uninitialized,
  38     /// The new memory is guaranteed to be zeroed.
  39     Zeroed,
  40 }
  41
  42 impl AllocInit {
  43     /// Initialize the specified memory block.
  44     ///
  45     /// This behaves like calling [`AllocInit::init_offset(memory, 0)`][off].
  46     ///
  47     /// [off]: AllocInit::init_offset
  48     ///
  49     /// # Safety
  50     ///
  51     /// * `memory.ptr` must be [valid] for writes of `memory.size` bytes.
  52     ///
  53     /// [valid]: ../../core/ptr/index.html#safety
  54     #[inline]
  55     #[unstable(feature = "allocator_api", issue = "32838")]
  56     pub unsafe fn init(self, memory: MemoryBlock) {
  57         self.init_offset(memory, 0)
  58     }
  59
  60     /// Initialize the memory block like specified by `init` at the specified `offset`.
  61     ///
  62     /// This is a no-op for [`AllocInit::Uninitialized`][] and writes zeroes for
  63     /// [`AllocInit::Zeroed`][] at `ptr + offset` until `ptr + layout.size()`.
  64     ///
  65     /// # Safety
  66     ///
  67     /// * `memory.ptr` must be [valid] for writes of `memory.size` bytes.
  68     /// * `offset` must be smaller than or equal to `memory.size`
  69     ///
  70     /// [valid]: ../../core/ptr/index.html#safety
  71     #[inline]
  72     #[unstable(feature = "allocator_api", issue = "32838")]
  73     pub unsafe fn init_offset(self, memory: MemoryBlock, offset: usize) {
  74         debug_assert!(
  75             offset <= memory.size,
  76             "`offset` must be smaller than or equal to `memory.size`"
  77         );
  78         match self {
  79             AllocInit::Uninitialized => (),
  80             AllocInit::Zeroed => {
  81                 memory.ptr.as_ptr().add(offset).write_bytes(0, memory.size - offset)
  82             }
  83         }
  84     }
  85 }
  86
  87 /// Represents a block of allocated memory returned by an allocator.
  88 #[derive(Debug, Copy, Clone)]
  89 #[unstable(feature = "allocator_api", issue = "32838")]
  90 pub struct MemoryBlock {
  91     pub ptr: NonNull<u8>,
  92     pub size: usize,
  93 }
  94
  95 /// A placement constraint when growing or shrinking an existing allocation.
  96 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
  97 #[unstable(feature = "allocator_api", issue = "32838")]
  98 pub enum ReallocPlacement {
  99     /// The allocator is allowed to move the allocation to a different memory address.
 100     // FIXME(wg-allocators#46): Add a section to the module documentation "What is a legal
 101     //                          allocator" and link it at "valid location".
 102     ///
 103     /// If the allocation _does_ move, it's the responsibility of the allocator
 104     /// to also move the data from the previous location to the new location.
 105     MayMove,
 106     /// The address of the new memory must not change.
 107     ///
 108     /// If the allocation would have to be moved to a new location to fit, the
 109     /// reallocation request will fail.
 110     InPlace,
 111 }
 112
 113 /// An implementation of `AllocRef` can allocate, grow, shrink, and deallocate arbitrary blocks of
 114 /// data described via [`Layout`][].
 115 ///
 116 /// `AllocRef` is designed to be implemented on ZSTs, references, or smart pointers because having
 117 /// an allocator like `MyAlloc([u8; N])` cannot be moved, without updating the pointers to the
 118 /// allocated memory.
 119 ///
 120 /// Unlike [`GlobalAlloc`][], zero-sized allocations are allowed in `AllocRef`. If an underlying
 121 /// allocator does not support this (like jemalloc) or return a null pointer (such as
 122 /// `libc::malloc`), this must be caught by the implementation.
 123 ///
 124 /// ### Currently allocated memory
 125 ///
 126 /// Some of the methods require that a memory block be *currently allocated* via an allocator. This
 127 /// means that:
 128 ///
 129 /// * the starting address for that memory block was previously returned by [`alloc`], [`grow`], or
 130 ///   [`shrink`], and
 131 ///
 132 /// * the memory block has not been subsequently deallocated, where blocks are either deallocated
 133 ///   directly by being passed to [`dealloc`] or were changed by being passed to [`grow`] or
 134 ///   [`shrink`] that returns `Ok`. If `grow` or `shrink` have returned `Err`, the passed pointer
 135 ///   remains valid.
 136 ///
 137 /// [`alloc`]: AllocRef::alloc
 138 /// [`grow`]: AllocRef::grow
 139 /// [`shrink`]: AllocRef::shrink
 140 /// [`dealloc`]: AllocRef::dealloc
 141 ///
 142 /// ### Memory fitting
 143 ///
 144 /// Some of the methods require that a layout *fit* a memory block. What it means for a layout to
 145 /// "fit" a memory block means (or equivalently, for a memory block to "fit" a layout) is that the
 146 /// following conditions must hold:
 147 ///
 148 /// * The block must be allocated with the same alignment as [`layout.align()`], and
 149 ///
 150 /// * The provided [`layout.size()`] must fall in the range `min ..= max`, where:
 151 ///   - `min` is the size of the layout most recently used to allocate the block, and
 152 ///   - `max` is the latest actual size returned from [`alloc`], [`grow`], or [`shrink`].
 153 ///
 154 /// [`layout.align()`]: Layout::align
 155 /// [`layout.size()`]: Layout::size
 156 ///
 157 /// # Safety
 158 ///
 159 /// * Memory blocks returned from an allocator must point to valid memory and retain their validity
 160 ///   until the instance and all of its clones are dropped,
 161 ///
 162 /// * cloning or moving the allocator must not invalidate memory blocks returned from this
 163 ///   allocator. A cloned allocator must behave like the same allocator, and
 164 ///
 165 /// * any pointer to a memory block which is [*currently allocated*] may be passed to any other
 166 ///   method of the allocator.
 167 ///
 168 /// [*currently allocated*]: #currently-allocated-memory
 169 #[unstable(feature = "allocator_api", issue = "32838")]
 170 pub unsafe trait AllocRef {
 171     /// Attempts to allocate a block of memory.
 172     ///
 173     /// On success, returns a [`MemoryBlock`][] meeting the size and alignment guarantees of `layout`.
 174     ///
 175     /// The returned block may have a larger size than specified by `layout.size()` and is
 176     /// initialized as specified by [`init`], all the way up to the returned size of the block.
 177     ///
 178     /// [`init`]: AllocInit
 179     ///
 180     /// # Errors
 181     ///
 182     /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet
 183     /// allocator's size or alignment constraints.
 184     ///
 185     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 186     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 187     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 188     ///
 189     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 190     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 191     ///
 192     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 193     fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr>;
 194
 195     /// Deallocates the memory referenced by `ptr`.
 196     ///
 197     /// # Safety
 198     ///
 199     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator, and
 200     /// * `layout` must [*fit*] that block of memory.
 201     ///
 202     /// [*currently allocated*]: #currently-allocated-memory
 203     /// [*fit*]: #memory-fitting
 204     unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
 205
 206     /// Attempts to extend the memory block.
 207     ///
 208     /// Returns a new [`MemoryBlock`][] containing a pointer and the actual size of the allocated
 209     /// memory. The pointer is suitable for holding data described by a new layout with `layout`’s
 210     /// alignment and a size given by `new_size`. To accomplish this, the allocator may extend the
 211     /// allocation referenced by `ptr` to fit the new layout. If the [`placement`] is
 212     /// [`InPlace`], the returned pointer is guaranteed to be the same as the passed `ptr`.
 213     ///
 214     /// If [`MayMove`] is used then ownership of the memory block referenced by `ptr`
 215     /// is transferred to this allocator. The memory may or may not be freed, and should be
 216     /// considered unusable (unless of course it is transferred back to the caller again via the
 217     /// return value of this method).
 218     ///
 219     /// If this method returns `Err`, then ownership of the memory block has not been transferred to
 220     /// this allocator, and the contents of the memory block are unaltered.
 221     ///
 222     /// The memory block will contain the following contents after a successful call to `grow`:
 223     ///   * Bytes `0..layout.size()` are preserved from the original allocation.
 224     ///   * Bytes `layout.size()..old_size` will either be preserved or initialized according to
 225     ///     [`init`], depending on the allocator implementation. `old_size` refers to the size of
 226     ///     the `MemoryBlock` prior to the `grow` call, which may be larger than the size
 227     ///     that was originally requested when it was allocated.
 228     ///   * Bytes `old_size..new_size` are initialized according to [`init`]. `new_size` refers to
 229     ///     the size of the `MemoryBlock` returned by the `grow` call.
 230     ///
 231     /// [`InPlace`]: ReallocPlacement::InPlace
 232     /// [`MayMove`]: ReallocPlacement::MayMove
 233     /// [`placement`]: ReallocPlacement
 234     /// [`init`]: AllocInit
 235     ///
 236     /// # Safety
 237     ///
 238     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator,
 239     /// * `layout` must [*fit*] that block of memory (The `new_size` argument need not fit it.),
 240     // We can't require that `new_size` is strictly greater than `memory.size` because of ZSTs.
 241     // An alternative would be
 242     // * `new_size must be strictly greater than `memory.size` or both are zero
 243     /// * `new_size` must be greater than or equal to `layout.size()`, and
 244     /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`, must not overflow
 245     ///   (i.e., the rounded value must be less than or equal to `usize::MAX`).
 246     ///
 247     /// [*currently allocated*]: #currently-allocated-memory
 248     /// [*fit*]: #memory-fitting
 249     ///
 250     /// # Errors
 251     ///
 252     /// Returns `Err` if the new layout does not meet the allocator's size and alignment
 253     /// constraints of the allocator, or if growing otherwise fails.
 254     ///
 255     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 256     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 257     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 258     ///
 259     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 260     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 261     ///
 262     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 263     unsafe fn grow(
 264         &mut self,
 265         ptr: NonNull<u8>,
 266         layout: Layout,
 267         new_size: usize,
 268         placement: ReallocPlacement,
 269         init: AllocInit,
 270     ) -> Result<MemoryBlock, AllocErr> {
 271         match placement {
 272             ReallocPlacement::InPlace => Err(AllocErr),
 273             ReallocPlacement::MayMove => {
 274                 let size = layout.size();
 275                 debug_assert!(
 276                     new_size >= size,
 277                     "`new_size` must be greater than or equal to `layout.size()`"
 278                 );
 279
 280                 if new_size == size {
 281                     return Ok(MemoryBlock { ptr, size });
 282                 }
 283
 284                 let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
 285                 let new_memory = self.alloc(new_layout, init)?;
 286                 ptr::copy_nonoverlapping(ptr.as_ptr(), new_memory.ptr.as_ptr(), size);
 287                 self.dealloc(ptr, layout);
 288                 Ok(new_memory)
 289             }
 290         }
 291     }
 292
 293     /// Attempts to shrink the memory block.
 294     ///
 295     /// Returns a new [`MemoryBlock`][] containing a pointer and the actual size of the allocated
 296     /// memory. The pointer is suitable for holding data described by a new layout with `layout`’s
 297     /// alignment and a size given by `new_size`. To accomplish this, the allocator may shrink the
 298     /// allocation referenced by `ptr` to fit the new layout. If the [`placement`] is
 299     /// [`InPlace`], the returned pointer is guaranteed to be the same as the passed `ptr`.
 300     ///
 301     /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been
 302     /// transferred to this allocator. The memory may or may not have been freed, and should be
 303     /// considered unusable unless it was transferred back to the caller again via the
 304     /// return value of this method.
 305     ///
 306     /// If this method returns `Err`, then ownership of the memory block has not been transferred to
 307     /// this allocator, and the contents of the memory block are unaltered.
 308     ///
 309     /// The behavior of how the allocator tries to shrink the memory is specified by [`placement`].
 310     ///
 311     /// [`InPlace`]: ReallocPlacement::InPlace
 312     /// [`placement`]: ReallocPlacement
 313     ///
 314     /// # Safety
 315     ///
 316     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator,
 317     /// * `layout` must [*fit*] that block of memory (The `new_size` argument need not fit it.), and
 318     // We can't require that `new_size` is strictly smaller than `memory.size` because of ZSTs.
 319     // An alternative would be
 320     // * `new_size must be strictly smaller than `memory.size` or both are zero
 321     /// * `new_size` must be smaller than or equal to `layout.size()`.
 322     ///
 323     /// [*currently allocated*]: #currently-allocated-memory
 324     /// [*fit*]: #memory-fitting
 325     ///
 326     /// # Errors
 327     ///
 328     /// Returns `Err` if the new layout does not meet the allocator's size and alignment
 329     /// constraints of the allocator, or if shrinking otherwise fails.
 330     ///
 331     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 332     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 333     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 334     ///
 335     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 336     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 337     ///
 338     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 339     unsafe fn shrink(
 340         &mut self,
 341         ptr: NonNull<u8>,
 342         layout: Layout,
 343         new_size: usize,
 344         placement: ReallocPlacement,
 345     ) -> Result<MemoryBlock, AllocErr> {
 346         match placement {
 347             ReallocPlacement::InPlace => Err(AllocErr),
 348             ReallocPlacement::MayMove => {
 349                 let size = layout.size();
 350                 debug_assert!(
 351                     new_size <= size,
 352                     "`new_size` must be smaller than or equal to `layout.size()`"
 353                 );
 354
 355                 if new_size == size {
 356                     return Ok(MemoryBlock { ptr, size });
 357                 }
 358
 359                 let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
 360                 let new_memory = self.alloc(new_layout, AllocInit::Uninitialized)?;
 361                 ptr::copy_nonoverlapping(ptr.as_ptr(), new_memory.ptr.as_ptr(), new_size);
 362                 self.dealloc(ptr, layout);
 363                 Ok(new_memory)
 364             }
 365         }
 366     }
 367 }