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