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(Copy, 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         // SAFETY: the safety contract for `init_offset` must be
  58         // upheld by the caller.
  59         unsafe { 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                 // SAFETY: the caller must guarantee that `offset` is smaller than or equal to `memory.size`,
  84                 // so the memory from `memory.ptr + offset` of length `memory.size - offset`
  85                 // is guaranteed to be contaned in `memory` and thus valid for writes.
  86                 unsafe { memory.ptr.as_ptr().add(offset).write_bytes(0, memory.size - offset) }
  87             }
  88         }
  89     }
  90 }
  91
  92 /// Represents a block of allocated memory returned by an allocator.
  93 #[derive(Debug, Copy, Clone)]
  94 #[unstable(feature = "allocator_api", issue = "32838")]
  95 pub struct MemoryBlock {
  96     pub ptr: NonNull<u8>,
  97     pub size: usize,
  98 }
  99
 100 /// A placement constraint when growing or shrinking an existing allocation.
 101 #[derive(Debug, Copy, Clone, PartialEq, Eq)]
 102 #[unstable(feature = "allocator_api", issue = "32838")]
 103 pub enum ReallocPlacement {
 104     /// The allocator is allowed to move the allocation to a different memory address.
 105     // FIXME(wg-allocators#46): Add a section to the module documentation "What is a legal
 106     //                          allocator" and link it at "valid location".
 107     ///
 108     /// If the allocation _does_ move, it's the responsibility of the allocator
 109     /// to also move the data from the previous location to the new location.
 110     MayMove,
 111     /// The address of the new memory must not change.
 112     ///
 113     /// If the allocation would have to be moved to a new location to fit, the
 114     /// reallocation request will fail.
 115     InPlace,
 116 }
 117
 118 /// An implementation of `AllocRef` can allocate, grow, shrink, and deallocate arbitrary blocks of
 119 /// data described via [`Layout`][].
 120 ///
 121 /// `AllocRef` is designed to be implemented on ZSTs, references, or smart pointers because having
 122 /// an allocator like `MyAlloc([u8; N])` cannot be moved, without updating the pointers to the
 123 /// allocated memory.
 124 ///
 125 /// Unlike [`GlobalAlloc`][], zero-sized allocations are allowed in `AllocRef`. If an underlying
 126 /// allocator does not support this (like jemalloc) or return a null pointer (such as
 127 /// `libc::malloc`), this must be caught by the implementation.
 128 ///
 129 /// ### Currently allocated memory
 130 ///
 131 /// Some of the methods require that a memory block be *currently allocated* via an allocator. This
 132 /// means that:
 133 ///
 134 /// * the starting address for that memory block was previously returned by [`alloc`], [`grow`], or
 135 ///   [`shrink`], and
 136 ///
 137 /// * the memory block has not been subsequently deallocated, where blocks are either deallocated
 138 ///   directly by being passed to [`dealloc`] or were changed by being passed to [`grow`] or
 139 ///   [`shrink`] that returns `Ok`. If `grow` or `shrink` have returned `Err`, the passed pointer
 140 ///   remains valid.
 141 ///
 142 /// [`alloc`]: AllocRef::alloc
 143 /// [`grow`]: AllocRef::grow
 144 /// [`shrink`]: AllocRef::shrink
 145 /// [`dealloc`]: AllocRef::dealloc
 146 ///
 147 /// ### Memory fitting
 148 ///
 149 /// Some of the methods require that a layout *fit* a memory block. What it means for a layout to
 150 /// "fit" a memory block means (or equivalently, for a memory block to "fit" a layout) is that the
 151 /// following conditions must hold:
 152 ///
 153 /// * The block must be allocated with the same alignment as [`layout.align()`], and
 154 ///
 155 /// * The provided [`layout.size()`] must fall in the range `min ..= max`, where:
 156 ///   - `min` is the size of the layout most recently used to allocate the block, and
 157 ///   - `max` is the latest actual size returned from [`alloc`], [`grow`], or [`shrink`].
 158 ///
 159 /// [`layout.align()`]: Layout::align
 160 /// [`layout.size()`]: Layout::size
 161 ///
 162 /// # Safety
 163 ///
 164 /// * Memory blocks returned from an allocator must point to valid memory and retain their validity
 165 ///   until the instance and all of its clones are dropped,
 166 ///
 167 /// * cloning or moving the allocator must not invalidate memory blocks returned from this
 168 ///   allocator. A cloned allocator must behave like the same allocator, and
 169 ///
 170 /// * any pointer to a memory block which is [*currently allocated*] may be passed to any other
 171 ///   method of the allocator.
 172 ///
 173 /// [*currently allocated*]: #currently-allocated-memory
 174 #[unstable(feature = "allocator_api", issue = "32838")]
 175 pub unsafe trait AllocRef {
 176     /// Attempts to allocate a block of memory.
 177     ///
 178     /// On success, returns a [`MemoryBlock`][] meeting the size and alignment guarantees of `layout`.
 179     ///
 180     /// The returned block may have a larger size than specified by `layout.size()` and is
 181     /// initialized as specified by [`init`], all the way up to the returned size of the block.
 182     ///
 183     /// [`init`]: AllocInit
 184     ///
 185     /// # Errors
 186     ///
 187     /// Returning `Err` indicates that either memory is exhausted or `layout` does not meet
 188     /// allocator's size or alignment constraints.
 189     ///
 190     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 191     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 192     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 193     ///
 194     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 195     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 196     ///
 197     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 198     fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr>;
 199
 200     /// Deallocates the memory referenced by `ptr`.
 201     ///
 202     /// # Safety
 203     ///
 204     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator, and
 205     /// * `layout` must [*fit*] that block of memory.
 206     ///
 207     /// [*currently allocated*]: #currently-allocated-memory
 208     /// [*fit*]: #memory-fitting
 209     unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
 210
 211     /// Attempts to extend the memory block.
 212     ///
 213     /// Returns a new [`MemoryBlock`][] containing a pointer and the actual size of the allocated
 214     /// memory. The pointer is suitable for holding data described by a new layout with `layout`’s
 215     /// alignment and a size given by `new_size`. To accomplish this, the allocator may extend the
 216     /// allocation referenced by `ptr` to fit the new layout. If the [`placement`] is
 217     /// [`InPlace`], the returned pointer is guaranteed to be the same as the passed `ptr`.
 218     ///
 219     /// If [`MayMove`] is used then ownership of the memory block referenced by `ptr`
 220     /// is transferred to this allocator. The memory may or may not be freed, and should be
 221     /// considered unusable (unless of course it is transferred back to the caller again via the
 222     /// return value of this method).
 223     ///
 224     /// If this method returns `Err`, then ownership of the memory block has not been transferred to
 225     /// this allocator, and the contents of the memory block are unaltered.
 226     ///
 227     /// The memory block will contain the following contents after a successful call to `grow`:
 228     ///   * Bytes `0..layout.size()` are preserved from the original allocation.
 229     ///   * Bytes `layout.size()..old_size` will either be preserved or initialized according to
 230     ///     [`init`], depending on the allocator implementation. `old_size` refers to the size of
 231     ///     the `MemoryBlock` prior to the `grow` call, which may be larger than the size
 232     ///     that was originally requested when it was allocated.
 233     ///   * Bytes `old_size..new_size` are initialized according to [`init`]. `new_size` refers to
 234     ///     the size of the `MemoryBlock` returned by the `grow` call.
 235     ///
 236     /// [`InPlace`]: ReallocPlacement::InPlace
 237     /// [`MayMove`]: ReallocPlacement::MayMove
 238     /// [`placement`]: ReallocPlacement
 239     /// [`init`]: AllocInit
 240     ///
 241     /// # Safety
 242     ///
 243     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator,
 244     /// * `layout` must [*fit*] that block of memory (The `new_size` argument need not fit it.),
 245     // We can't require that `new_size` is strictly greater than `memory.size` because of ZSTs.
 246     // An alternative would be
 247     // * `new_size must be strictly greater than `memory.size` or both are zero
 248     /// * `new_size` must be greater than or equal to `layout.size()`, and
 249     /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`, must not overflow
 250     ///   (i.e., the rounded value must be less than or equal to `usize::MAX`).
 251     ///
 252     /// [*currently allocated*]: #currently-allocated-memory
 253     /// [*fit*]: #memory-fitting
 254     ///
 255     /// # Errors
 256     ///
 257     /// Returns `Err` if the new layout does not meet the allocator's size and alignment
 258     /// constraints of the allocator, or if growing otherwise fails.
 259     ///
 260     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 261     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 262     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 263     ///
 264     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 265     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 266     ///
 267     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 268     unsafe fn grow(
 269         &mut self,
 270         ptr: NonNull<u8>,
 271         layout: Layout,
 272         new_size: usize,
 273         placement: ReallocPlacement,
 274         init: AllocInit,
 275     ) -> Result<MemoryBlock, AllocErr> {
 276         match placement {
 277             ReallocPlacement::InPlace => Err(AllocErr),
 278             ReallocPlacement::MayMove => {
 279                 let size = layout.size();
 280                 debug_assert!(
 281                     new_size >= size,
 282                     "`new_size` must be greater than or equal to `layout.size()`"
 283                 );
 284
 285                 if new_size == size {
 286                     return Ok(MemoryBlock { ptr, size });
 287                 }
 288
 289                 let new_layout =
 290                     // SAFETY: the caller must ensure that the `new_size` does not overflow.
 291                     // `layout.align()` comes from a `Layout` and is thus guaranteed to be valid for a Layout.
 292                     // The caller must ensure that `new_size` is greater than zero.
 293                     unsafe { Layout::from_size_align_unchecked(new_size, layout.align()) };
 294                 let new_memory = self.alloc(new_layout, init)?;
 295
 296                 // SAFETY: because `new_size` must be greater than or equal to `size`, both the old and new
 297                 // memory allocation are valid for reads and writes for `size` bytes. Also, because the old
 298                 // allocation wasn't yet deallocated, it cannot overlap `new_memory`. Thus, the call to
 299                 // `copy_nonoverlapping` is safe.
 300                 // The safety contract for `dealloc` must be upheld by the caller.
 301                 unsafe {
 302                     ptr::copy_nonoverlapping(ptr.as_ptr(), new_memory.ptr.as_ptr(), size);
 303                     self.dealloc(ptr, layout);
 304                     Ok(new_memory)
 305                 }
 306             }
 307         }
 308     }
 309
 310     /// Attempts to shrink the memory block.
 311     ///
 312     /// Returns a new [`MemoryBlock`][] containing a pointer and the actual size of the allocated
 313     /// memory. The pointer is suitable for holding data described by a new layout with `layout`’s
 314     /// alignment and a size given by `new_size`. To accomplish this, the allocator may shrink the
 315     /// allocation referenced by `ptr` to fit the new layout. If the [`placement`] is
 316     /// [`InPlace`], the returned pointer is guaranteed to be the same as the passed `ptr`.
 317     ///
 318     /// If this returns `Ok`, then ownership of the memory block referenced by `ptr` has been
 319     /// transferred to this allocator. The memory may or may not have been freed, and should be
 320     /// considered unusable unless it was transferred back to the caller again via the
 321     /// return value of this method.
 322     ///
 323     /// If this method returns `Err`, then ownership of the memory block has not been transferred to
 324     /// this allocator, and the contents of the memory block are unaltered.
 325     ///
 326     /// The behavior of how the allocator tries to shrink the memory is specified by [`placement`].
 327     ///
 328     /// [`InPlace`]: ReallocPlacement::InPlace
 329     /// [`placement`]: ReallocPlacement
 330     ///
 331     /// # Safety
 332     ///
 333     /// * `ptr` must denote a block of memory [*currently allocated*] via this allocator,
 334     /// * `layout` must [*fit*] that block of memory (The `new_size` argument need not fit it.), and
 335     // We can't require that `new_size` is strictly smaller than `memory.size` because of ZSTs.
 336     // An alternative would be
 337     // * `new_size must be strictly smaller than `memory.size` or both are zero
 338     /// * `new_size` must be smaller than or equal to `layout.size()`.
 339     ///
 340     /// [*currently allocated*]: #currently-allocated-memory
 341     /// [*fit*]: #memory-fitting
 342     ///
 343     /// # Errors
 344     ///
 345     /// Returns `Err` if the new layout does not meet the allocator's size and alignment
 346     /// constraints of the allocator, or if shrinking otherwise fails.
 347     ///
 348     /// Implementations are encouraged to return `Err` on memory exhaustion rather than panicking or
 349     /// aborting, but this is not a strict requirement. (Specifically: it is *legal* to implement
 350     /// this trait atop an underlying native allocation library that aborts on memory exhaustion.)
 351     ///
 352     /// Clients wishing to abort computation in response to an allocation error are encouraged to
 353     /// call the [`handle_alloc_error`] function, rather than directly invoking `panic!` or similar.
 354     ///
 355     /// [`handle_alloc_error`]: ../../alloc/alloc/fn.handle_alloc_error.html
 356     unsafe fn shrink(
 357         &mut self,
 358         ptr: NonNull<u8>,
 359         layout: Layout,
 360         new_size: usize,
 361         placement: ReallocPlacement,
 362     ) -> Result<MemoryBlock, AllocErr> {
 363         match placement {
 364             ReallocPlacement::InPlace => Err(AllocErr),
 365             ReallocPlacement::MayMove => {
 366                 let size = layout.size();
 367                 debug_assert!(
 368                     new_size <= size,
 369                     "`new_size` must be smaller than or equal to `layout.size()`"
 370                 );
 371
 372                 if new_size == size {
 373                     return Ok(MemoryBlock { ptr, size });
 374                 }
 375
 376                 let new_layout =
 377                 // SAFETY: the caller must ensure that the `new_size` does not overflow.
 378                 // `layout.align()` comes from a `Layout` and is thus guaranteed to be valid for a Layout.
 379                 // The caller must ensure that `new_size` is greater than zero.
 380                     unsafe { Layout::from_size_align_unchecked(new_size, layout.align()) };
 381                 let new_memory = self.alloc(new_layout, AllocInit::Uninitialized)?;
 382
 383                 // SAFETY: because `new_size` must be lower than or equal to `size`, both the old and new
 384                 // memory allocation are valid for reads and writes for `new_size` bytes. Also, because the
 385                 // old allocation wasn't yet deallocated, it cannot overlap `new_memory`. Thus, the call to
 386                 // `copy_nonoverlapping` is safe.
 387                 // The safety contract for `dealloc` must be upheld by the caller.
 388                 unsafe {
 389                     ptr::copy_nonoverlapping(ptr.as_ptr(), new_memory.ptr.as_ptr(), new_size);
 390                     self.dealloc(ptr, layout);
 391                     Ok(new_memory)
 392                 }
 393             }
 394         }
 395     }
 396
 397     /// Creates a "by reference" adaptor for this instance of `AllocRef`.
 398     ///
 399     /// The returned adaptor also implements `AllocRef` and will simply borrow this.
 400     #[inline(always)]
 401     fn by_ref(&mut self) -> &mut Self {
 402         self
 403     }
 404 }
 405
 406 #[unstable(feature = "allocator_api", issue = "32838")]
 407 unsafe impl<A> AllocRef for &mut A
 408 where
 409     A: AllocRef + ?Sized,
 410 {
 411     #[inline]
 412     fn alloc(&mut self, layout: Layout, init: AllocInit) -> Result<MemoryBlock, AllocErr> {
 413         (**self).alloc(layout, init)
 414     }
 415
 416     #[inline]
 417     unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
 418         // SAFETY: the safety contract must be upheld by the caller
 419         unsafe { (**self).dealloc(ptr, layout) }
 420     }
 421
 422     #[inline]
 423     unsafe fn grow(
 424         &mut self,
 425         ptr: NonNull<u8>,
 426         layout: Layout,
 427         new_size: usize,
 428         placement: ReallocPlacement,
 429         init: AllocInit,
 430     ) -> Result<MemoryBlock, AllocErr> {
 431         // SAFETY: the safety contract must be upheld by the caller
 432         unsafe { (**self).grow(ptr, layout, new_size, placement, init) }
 433     }
 434
 435     #[inline]
 436     unsafe fn shrink(
 437         &mut self,
 438         ptr: NonNull<u8>,
 439         layout: Layout,
 440         new_size: usize,
 441         placement: ReallocPlacement,
 442     ) -> Result<MemoryBlock, AllocErr> {
 443         // SAFETY: the safety contract must be upheld by the caller
 444         unsafe { (**self).shrink(ptr, layout, new_size, placement) }
 445     }
 446 }