Document memory allocation APIs

Add some docs where they were missing,
attempt to fix them where they were out of date.

4 files changed, 245 insertions, 50 deletions

diff --git a/src/liballoc/alloc.rs b/src/liballoc/alloc.rs
index 710da9a475b..c9430a29e4c 100644
--- a/src/liballoc/alloc.rs
+++ b/src/liballoc/alloc.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+//! Memory allocation APIs
+
 #![unstable(feature = "allocator_api",
             reason = "the precise API and guarantees it provides may be tweaked \
                       slightly, especially to possibly take into account the \
@@ -37,27 +39,80 @@ extern "Rust" {
     fn __rust_alloc_zeroed(size: usize, align: usize) -> *mut u8;
 }
 
+/// The global memory allocator.
+///
+/// This type implements the [`Alloc`] trait by forwarding calls
+/// to the allocator registered with the `#[global_allocator]` attribute
+/// if there is one, or the `std` crate’s default.
 #[derive(Copy, Clone, Default, Debug)]
 pub struct Global;
 
+/// Allocate memory with the global allocator.
+///
+/// This function forwards calls to the [`GlobalAlloc::alloc`] method
+/// of the allocator registered with the `#[global_allocator]` attribute
+/// if there is one, or the `std` crate’s default.
+///
+/// This function is expected to be deprecated in favor of the `alloc` method
+/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+///
+/// # Safety
+///
+/// See [`GlobalAlloc::alloc`].
 #[unstable(feature = "allocator_api", issue = "32838")]
 #[inline]
 pub unsafe fn alloc(layout: Layout) -> *mut u8 {
     __rust_alloc(layout.size(), layout.align())
 }
 
+/// Deallocate memory with the global allocator.
+///
+/// This function forwards calls to the [`GlobalAlloc::dealloc`] method
+/// of the allocator registered with the `#[global_allocator]` attribute
+/// if there is one, or the `std` crate’s default.
+///
+/// This function is expected to be deprecated in favor of the `dealloc` method
+/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+///
+/// # Safety
+///
+/// See [`GlobalAlloc::dealloc`].
 #[unstable(feature = "allocator_api", issue = "32838")]
 #[inline]
 pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) {
     __rust_dealloc(ptr, layout.size(), layout.align())
 }
 
+/// Reallocate memory with the global allocator.
+///
+/// This function forwards calls to the [`GlobalAlloc::realloc`] method
+/// of the allocator registered with the `#[global_allocator]` attribute
+/// if there is one, or the `std` crate’s default.
+///
+/// This function is expected to be deprecated in favor of the `realloc` method
+/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+///
+/// # Safety
+///
+/// See [`GlobalAlloc::realloc`].
 #[unstable(feature = "allocator_api", issue = "32838")]
 #[inline]
 pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
     __rust_realloc(ptr, layout.size(), layout.align(), new_size)
 }
 
+/// Allocate zero-initialized memory with the global allocator.
+///
+/// This function forwards calls to the [`GlobalAlloc::alloc_zeroed`] method
+/// of the allocator registered with the `#[global_allocator]` attribute
+/// if there is one, or the `std` crate’s default.
+///
+/// This function is expected to be deprecated in favor of the `alloc_zeroed` method
+/// of the [`Global`] type when it and the [`Alloc`] trait become stable.
+///
+/// # Safety
+///
+/// See [`GlobalAlloc::alloc_zeroed`].
 #[unstable(feature = "allocator_api", issue = "32838")]
 #[inline]
 pub unsafe fn alloc_zeroed(layout: Layout) -> *mut u8 {
@@ -123,6 +178,16 @@ pub(crate) unsafe fn box_free<T: ?Sized>(ptr: Unique<T>) {
     }
 }
 
+/// Abort on memory allocation error or failure.
+///
+/// Callers of memory allocation APIs wishing to abort computation
+/// in response to an allocation error are encouraged to call this function,
+/// rather than directly invoking `panic!` or similar.
+///
+/// The default behavior of this function is to print a message to standard error
+/// and abort the process.
+/// It can be replaced with [`std::alloc::set_oom_hook`]
+/// and [`std::alloc::take_oom_hook`].
 #[rustc_allocator_nounwind]
 pub fn oom(layout: Layout) -> ! {
     #[allow(improper_ctypes)]
diff --git a/src/liballoc_system/lib.rs b/src/liballoc_system/lib.rs
index 82fda8d639e..85bf43a5429 100644
--- a/src/liballoc_system/lib.rs
+++ b/src/liballoc_system/lib.rs
@@ -44,6 +44,7 @@ const MIN_ALIGN: usize = 16;
 use core::alloc::{Alloc, GlobalAlloc, AllocErr, Layout};
 use core::ptr::NonNull;
 
+/// The default memory allocator provided by the operating system.
 #[unstable(feature = "allocator_api", issue = "32838")]
 pub struct System;
 
diff --git a/src/libcore/alloc.rs b/src/libcore/alloc.rs
index 2815ef6400d..8fcd8555cdc 100644
--- a/src/libcore/alloc.rs
+++ b/src/libcore/alloc.rs
@@ -8,6 +8,8 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
+//! Memory allocation APIs
+
 #![unstable(feature = "allocator_api",
             reason = "the precise API and guarantees it provides may be tweaked \
                       slightly, especially to possibly take into account the \
@@ -315,8 +317,9 @@ impl Layout {
     }
 }
 
-/// The parameters given to `Layout::from_size_align` do not satisfy
-/// its documented constraints.
+/// The parameters given to `Layout::from_size_align`
+/// or some other `Layout` constructor
+/// do not satisfy its documented constraints.
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct LayoutErr {
     private: ()
@@ -329,8 +332,8 @@ impl fmt::Display for LayoutErr {
     }
 }
 
-/// The `AllocErr` error specifies whether an allocation failure is
-/// specifically due to resource exhaustion or if it is due to
+/// The `AllocErr` error indicates an allocation failure
+/// that may be due to resource exhaustion or to
 /// something wrong when combining the given input arguments with this
 /// allocator.
 #[derive(Clone, PartialEq, Eq, Debug)]
@@ -346,6 +349,7 @@ impl fmt::Display for AllocErr {
 /// The `CannotReallocInPlace` error is used when `grow_in_place` or
 /// `shrink_in_place` were unable to reuse the given memory block for
 /// a requested layout.
+// FIXME: should this be in libcore or liballoc?
 #[derive(Clone, PartialEq, Eq, Debug)]
 pub struct CannotReallocInPlace;
 
@@ -363,6 +367,7 @@ impl fmt::Display for CannotReallocInPlace {
 }
 
 /// Augments `AllocErr` with a CapacityOverflow variant.
+// FIXME: should this be in libcore or liballoc?
 #[derive(Clone, PartialEq, Eq, Debug)]
 #[unstable(feature = "try_reserve", reason = "new API", issue="48043")]
 pub enum CollectionAllocErr {
@@ -389,27 +394,125 @@ impl From<LayoutErr> for CollectionAllocErr {
     }
 }
 
-/// A memory allocator that can be registered to be the one backing `std::alloc::Global`
+/// A memory allocator that can be registered as the standard library’s default
 /// though the `#[global_allocator]` attributes.
+///
+/// Some of the methods require that a memory block be *currently
+/// allocated* via an allocator. This means that:
+///
+/// * the starting address for that memory block was previously
+///   returned by a previous call to an allocation method
+///   such as `alloc`, and
+///
+/// * the memory block has not been subsequently deallocated, where
+///   blocks are deallocated either by being passed to a deallocation
+///   method such as `dealloc` or by being
+///   passed to a reallocation method that returns a non-null pointer.
+///
+///
+/// # Example
+///
+/// ```no_run
+/// use std::alloc::{GlobalAlloc, Layout, alloc};
+/// use std::ptr::null_mut;
+///
+/// struct MyAllocator;
+///
+/// unsafe impl GlobalAlloc for MyAllocator {
+///     unsafe fn alloc(&self, _layout: Layout) -> *mut u8 { null_mut() }
+///     unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {}
+/// }
+///
+/// #[global_allocator]
+/// static A: MyAllocator = MyAllocator;
+///
+/// fn main() {
+///     unsafe {
+///         assert!(alloc(Layout::new::<u32>()).is_null())
+///     }
+/// }
+/// ```
+///
+/// # Unsafety
+///
+/// The `GlobalAlloc` trait is an `unsafe` trait for a number of reasons, and
+/// implementors must ensure that they adhere to these contracts:
+///
+/// * Pointers returned from allocation functions must point to valid memory and
+///   retain their validity until at least the instance of `GlobalAlloc` is dropped
+///   itself.
+///
+/// * It's undefined behavior if global allocators unwind.  This restriction may
+///   be lifted in the future, but currently a panic from any of these
+///   functions may lead to memory unsafety.
+///
+/// * `Layout` queries and calculations in general must be correct. Callers of
+///   this trait are allowed to rely on the contracts defined on each method,
+///   and implementors must ensure such contracts remain true.
 pub unsafe trait GlobalAlloc {
     /// Allocate memory as described by the given `layout`.
     ///
     /// Returns a pointer to newly-allocated memory,
-    /// or NULL to indicate allocation failure.
+    /// or null to indicate allocation failure.
     ///
     /// # Safety
     ///
-    /// **FIXME:** what are the exact requirements?
+    /// This function is unsafe because undefined behavior can result
+    /// if the caller does not ensure that `layout` has non-zero size.
+    ///
+    /// (Extension subtraits might provide more specific bounds on
+    /// behavior, e.g. guarantee a sentinel address or a null pointer
+    /// in response to a zero-size allocation request.)
+    ///
+    /// The allocated block of memory may or may not be initialized.
+    ///
+    /// # Errors
+    ///
+    /// Returning a null pointer indicates that either memory is exhausted
+    /// or `layout` does not meet allocator's size or alignment constraints.
+    ///
+    /// Implementations are encouraged to return null on memory
+    /// exhaustion rather than aborting, but this is not
+    /// a strict requirement. (Specifically: it is *legal* to
+    /// implement this trait atop an underlying native allocation
+    /// library that aborts on memory exhaustion.)
+    ///
+    /// Clients wishing to abort computation in response to an
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn alloc(&self, layout: Layout) -> *mut u8;
 
     /// Deallocate the block of memory at the given `ptr` pointer with the given `layout`.
     ///
     /// # Safety
     ///
-    /// **FIXME:** what are the exact requirements?
-    /// In particular around layout *fit*. (See docs for the `Alloc` trait.)
+    /// This function is unsafe because undefined behavior can result
+    /// if the caller does not ensure all of the following:
+    ///
+    /// * `ptr` must denote a block of memory currently allocated via
+    ///   this allocator,
+    ///
+    /// * `layout` must be the same layout that was used
+    ///   to allocated that block of memory,
     unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout);
 
+    /// Behaves like `alloc`, but also ensures that the contents
+    /// are set to zero before being returned.
+    ///
+    /// # Safety
+    ///
+    /// This function is unsafe for the same reasons that `alloc` is.
+    /// However the allocated block of memory is guaranteed to be initialized.
+    ///
+    /// # Errors
+    ///
+    /// Returning a null pointer indicates that either memory is exhausted
+    /// or `layout` does not meet allocator's size or alignment constraints,
+    /// just as in `alloc`.
+    ///
+    /// Clients wishing to abort computation in response to an
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
         let size = layout.size();
         let ptr = self.alloc(layout);
@@ -422,19 +525,51 @@ pub unsafe trait GlobalAlloc {
     /// Shink or grow a block of memory to the given `new_size`.
     /// The block is described by the given `ptr` pointer and `layout`.
     ///
-    /// Return a new pointer (which may or may not be the same as `ptr`),
-    /// or NULL to indicate reallocation failure.
+    /// If this returns a non-null pointer, then ownership of the memory block
+    /// referenced by `ptr` has been transferred to this alloctor.
+    /// The memory may or may not have been deallocated,
+    /// and should be considered unusable (unless of course it was
+    /// transferred back to the caller again via the return value of
+    /// this method).
     ///
-    /// If reallocation is successful, the old `ptr` pointer is considered
-    /// to have been deallocated.
+    /// If this method returns null, then ownership of the memory
+    /// block has not been transferred to this allocator, and the
+    /// contents of the memory block are unaltered.
     ///
     /// # Safety
     ///
-    /// `new_size`, when rounded up to the nearest multiple of `old_layout.align()`,
-    /// must not overflow (i.e. the rounded value must be less than `usize::MAX`).
+    /// This function is unsafe because undefined behavior can result
+    /// if the caller does not ensure all of the following:
+    ///
+    /// * `ptr` must be currently allocated via this allocator,
+    ///
+    /// * `layout` must be the same layout that was used
+    ///   to allocated that block of memory,
+    ///
+    /// * `new_size` must be greater than zero.
+    ///
+    /// * `new_size`, when rounded up to the nearest multiple of `layout.align()`,
+    ///   must not overflow (i.e. the rounded value must be less than `usize::MAX`).
+    ///
+    /// (Extension subtraits might provide more specific bounds on
+    /// behavior, e.g. guarantee a sentinel address or a null pointer
+    /// in response to a zero-size allocation request.)
+    ///
+    /// # Errors
+    ///
+    /// Returns null if the new layout does not meet the size
+    /// and alignment constraints of the allocator, or if reallocation
+    /// otherwise fails.
+    ///
+    /// Implementations are encouraged to return null on memory
+    /// exhaustion rather than panicking or aborting, but this is not
+    /// a strict requirement. (Specifically: it is *legal* to
+    /// implement this trait atop an underlying native allocation
+    /// library that aborts on memory exhaustion.)
     ///
-    /// **FIXME:** what are the exact requirements?
-    /// In particular around layout *fit*. (See docs for the `Alloc` trait.)
+    /// Clients wishing to abort computation in response to a
+    /// reallocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
         let new_layout = Layout::from_size_align_unchecked(new_size, layout.align());
         let new_ptr = self.alloc(new_layout);
@@ -523,27 +658,21 @@ pub unsafe trait GlobalAlloc {
 ///   retain their validity until at least the instance of `Alloc` is dropped
 ///   itself.
 ///
-/// * It's undefined behavior if global allocators unwind.  This restriction may
-///   be lifted in the future, but currently a panic from any of these
-///   functions may lead to memory unsafety. Note that as of the time of this
-///   writing allocators *not* intending to be global allocators can still panic
-///   in their implementation without violating memory safety.
-///
 /// * `Layout` queries and calculations in general must be correct. Callers of
 ///   this trait are allowed to rely on the contracts defined on each method,
 ///   and implementors must ensure such contracts remain true.
 ///
 /// Note that this list may get tweaked over time as clarifications are made in
-/// the future. Additionally global allocators may gain unique requirements for
-/// how to safely implement one in the future as well.
+/// the future.
 pub unsafe trait Alloc {
 
-    // (Note: existing allocators have unspecified but well-defined
+    // (Note: some existing allocators have unspecified but well-defined
     // behavior in response to a zero size allocation request ;
     // e.g. in C, `malloc` of 0 will either return a null pointer or a
     // unique pointer, but will not have arbitrary undefined
-    // behavior. Rust should consider revising the alloc::heap crate
-    // to reflect this reality.)
+    // behavior.
+    // However in jemalloc for example,
+    // `mallocx(0)` is documented as undefined behavior.)
 
     /// Returns a pointer meeting the size and alignment guarantees of
     /// `layout`.
@@ -579,8 +708,8 @@ pub unsafe trait Alloc {
     /// library that aborts on memory exhaustion.)
     ///
     /// Clients wishing to abort computation in response to an
-    /// allocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// allocation error are encouraged to call the `oom` function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr>;
 
     /// Deallocate the memory referenced by `ptr`.
@@ -686,9 +815,9 @@ pub unsafe trait Alloc {
     /// implement this trait atop an underlying native allocation
     /// library that aborts on memory exhaustion.)
     ///
-    /// Clients wishing to abort computation in response to an
-    /// reallocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// Clients wishing to abort computation in response to a
+    /// reallocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn realloc(&mut self,
                       ptr: NonNull<u8>,
                       layout: Layout,
@@ -731,8 +860,8 @@ pub unsafe trait Alloc {
     /// constraints, just as in `alloc`.
     ///
     /// Clients wishing to abort computation in response to an
-    /// allocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn alloc_zeroed(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr> {
         let size = layout.size();
         let p = self.alloc(layout);
@@ -757,8 +886,8 @@ pub unsafe trait Alloc {
     /// constraints, just as in `alloc`.
     ///
     /// Clients wishing to abort computation in response to an
-    /// allocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn alloc_excess(&mut self, layout: Layout) -> Result<Excess, AllocErr> {
         let usable_size = self.usable_size(&layout);
         self.alloc(layout).map(|p| Excess(p, usable_size.1))
@@ -778,9 +907,9 @@ pub unsafe trait Alloc {
     /// `layout` does not meet allocator's size or alignment
     /// constraints, just as in `realloc`.
     ///
-    /// Clients wishing to abort computation in response to an
-    /// reallocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// Clients wishing to abort computation in response to a
+    /// reallocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn realloc_excess(&mut self,
                              ptr: NonNull<u8>,
                              layout: Layout,
@@ -823,7 +952,7 @@ pub unsafe trait Alloc {
     /// could fit `layout`.
     ///
     /// Note that one cannot pass `CannotReallocInPlace` to the `oom`
-    /// method; clients are expected either to be able to recover from
+    /// function; clients are expected either to be able to recover from
     /// `grow_in_place` failures without aborting, or to fall back on
     /// another reallocation method before resorting to an abort.
     unsafe fn grow_in_place(&mut self,
@@ -878,7 +1007,7 @@ pub unsafe trait Alloc {
     /// could fit `layout`.
     ///
     /// Note that one cannot pass `CannotReallocInPlace` to the `oom`
-    /// method; clients are expected either to be able to recover from
+    /// function; clients are expected either to be able to recover from
     /// `shrink_in_place` failures without aborting, or to fall back
     /// on another reallocation method before resorting to an abort.
     unsafe fn shrink_in_place(&mut self,
@@ -926,8 +1055,8 @@ pub unsafe trait Alloc {
     /// will *not* yield undefined behavior.
     ///
     /// Clients wishing to abort computation in response to an
-    /// allocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     fn alloc_one<T>(&mut self) -> Result<NonNull<T>, AllocErr>
         where Self: Sized
     {
@@ -993,8 +1122,8 @@ pub unsafe trait Alloc {
     /// Always returns `Err` on arithmetic overflow.
     ///
     /// Clients wishing to abort computation in response to an
-    /// allocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// allocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     fn alloc_array<T>(&mut self, n: usize) -> Result<NonNull<T>, AllocErr>
         where Self: Sized
     {
@@ -1037,9 +1166,9 @@ pub unsafe trait Alloc {
     ///
     /// Always returns `Err` on arithmetic overflow.
     ///
-    /// Clients wishing to abort computation in response to an
-    /// reallocation error are encouraged to call the allocator's `oom`
-    /// method, rather than directly invoking `panic!` or similar.
+    /// Clients wishing to abort computation in response to a
+    /// reallocation error are encouraged to call the [`oom`] function,
+    /// rather than directly invoking `panic!` or similar.
     unsafe fn realloc_array<T>(&mut self,
                                ptr: NonNull<T>,
                                n_old: usize,
diff --git a/src/libstd/alloc.rs b/src/libstd/alloc.rs
index 9904634f1fa..9126155a7c9 100644
--- a/src/libstd/alloc.rs
+++ b/src/libstd/alloc.rs
@@ -8,7 +8,7 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-//! dox
+//! Memory allocation APIs
 
 #![unstable(issue = "32838", feature = "allocator_api")]