Auto merge of #49669 - SimonSapin:global-alloc, r=alexcrichton

Add GlobalAlloc trait + tweaks for initial stabilization

This is the outcome of discussion at the Rust All Hands in Berlin. The high-level goal is stabilizing sooner rather than later the ability to [change the global allocator](https://github.com/rust-lang/rust/issues/27389), as well as allocating memory without abusing `Vec::with_capacity` + `mem::forget`.

Since we’re not ready to settle every detail of the `Alloc` trait for the purpose of collections that are generic over the allocator type (for example the possibility of a separate trait for deallocation only, and what that would look like exactly), we propose introducing separately **a new `GlobalAlloc` trait**, for use with the `#[global_allocator]` attribute.

We also propose a number of changes to existing APIs. They are batched in this one PR in order to minimize disruption to Nightly users.

The plan for initial stabilization is detailed in the tracking issue https://github.com/rust-lang/rust/issues/49668.

CC @rust-lang/libs, @glandium

## Immediate breaking changes to unstable features

* For pointers to allocated memory, change the pointed type from `u8` to `Opaque`, a new public [extern type](https://github.com/rust-lang/rust/issues/43467). Since extern types are not `Sized`, `<*mut _>::offset` cannot be used without first casting to another pointer type. (We hope that extern types can also be stabilized soon.)
* In the `Alloc` trait, change these pointers to `ptr::NonNull` and change the `AllocErr` type to a zero-size struct. This makes return types `Result<ptr::NonNull<Opaque>, AllocErr>` be pointer-sized.
* Instead of a new `Layout`, `realloc` takes only a new size (in addition to the pointer and old `Layout`). Changing the alignment is not supported with `realloc`.
* Change the return type of `Layout::from_size_align` from `Option<Self>` to `Result<Self, LayoutErr>`, with `LayoutErr` a new opaque struct.
* A `static` item registered as the global allocator with the `#[global_allocator]` **must now implement the new `GlobalAlloc` trait** instead of `Alloc`.

## Eventually-breaking changes to unstable features, with a deprecation period

* Rename the respective `heap` modules to `alloc` in the `core`, `alloc`, and `std` crates. (Yes, this does mean that `::alloc::alloc::Alloc::alloc` is a valid path to a trait method if you have `exetrn crate alloc;`)
* Rename the the `Heap` type to `Global`, since it is the entry point for what’s registered with `#[global_allocator]`.

Old names remain available for now, as deprecated `pub use` reexports.

## Backward-compatible changes

* Add a new [extern type](https://github.com/rust-lang/rust/issues/43467) `Opaque`, for use in pointers to allocated memory.
* Add a new `GlobalAlloc` trait shown below. Unlike `Alloc`, it uses bare `*mut Opaque` without `NonNull` or `Result`. NULL in return values indicates an error (of unspecified nature). This is easier to implement on top of `malloc`-like APIs.
* Add impls of `GlobalAlloc` for both the `Global` and `System` types, in addition to existing impls of `Alloc`. This enables calling `GlobalAlloc` methods on the stable channel before `Alloc` is stable. Implementing two traits with identical method names can make some calls ambiguous, but most code is expected to have no more than one of the two traits in scope. Erroneous code like `use std::alloc::Global; #[global_allocator] static A: Global = Global;` (where `Global` is defined to call itself, causing infinite recursion) is not statically prevented by the type system, but we count on it being hard enough to do accidentally and easy enough to diagnose.

```rust
extern {
    pub type Opaque;
}

pub unsafe trait GlobalAlloc {
    unsafe fn alloc(&self, layout: Layout) -> *mut Opaque;
    unsafe fn dealloc(&self, ptr: *mut Opaque, layout: Layout);

    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut Opaque {
        // Default impl: self.alloc() and ptr::write_bytes()
    }
    unsafe fn realloc(&self, ptr: *mut Opaque, old_layout: Layout, new_size: usize) -> *mut Opaque {
        // Default impl: self.alloc() and ptr::copy_nonoverlapping() and self.dealloc()
    }

    fn oom(&self) -> ! {
        // intrinsics::abort
    }

    // More methods with default impls may be added in the future
}
```

## Bikeshed

The tracking issue https://github.com/rust-lang/rust/issues/49668 lists some open questions. If consensus is reached before this PR is merged, changes can be integrated.

2 files changed, 8 insertions, 118 deletions

diff --git a/src/liballoc_jemalloc/Cargo.toml b/src/liballoc_jemalloc/Cargo.toml
index fd4a4553046..02435170374 100644
--- a/src/liballoc_jemalloc/Cargo.toml
+++ b/src/liballoc_jemalloc/Cargo.toml
@@ -12,7 +12,6 @@ test = false
 doc = false
 
 [dependencies]
-alloc = { path = "../liballoc" }
 alloc_system = { path = "../liballoc_system" }
 core = { path = "../libcore" }
 libc = { path = "../rustc/libc_shim" }
diff --git a/src/liballoc_jemalloc/lib.rs b/src/liballoc_jemalloc/lib.rs
index df7e3f61f5f..2b66c293f21 100644
--- a/src/liballoc_jemalloc/lib.rs
+++ b/src/liballoc_jemalloc/lib.rs
@@ -30,9 +30,7 @@ extern crate libc;
 pub use contents::*;
 #[cfg(not(dummy_jemalloc))]
 mod contents {
-    use core::ptr;
-
-    use core::heap::{Alloc, AllocErr, Layout};
+    use core::alloc::GlobalAlloc;
     use alloc_system::System;
     use libc::{c_int, c_void, size_t};
 
@@ -54,16 +52,8 @@ mod contents {
         fn rallocx(ptr: *mut c_void, size: size_t, flags: c_int) -> *mut c_void;
         #[cfg_attr(any(target_os = "macos", target_os = "android", target_os = "ios",
                        target_os = "dragonfly", target_os = "windows", target_env = "musl"),
-                   link_name = "je_xallocx")]
-        fn xallocx(ptr: *mut c_void, size: size_t, extra: size_t, flags: c_int) -> size_t;
-        #[cfg_attr(any(target_os = "macos", target_os = "android", target_os = "ios",
-                       target_os = "dragonfly", target_os = "windows", target_env = "musl"),
                    link_name = "je_sdallocx")]
         fn sdallocx(ptr: *mut c_void, size: size_t, flags: c_int);
-        #[cfg_attr(any(target_os = "macos", target_os = "android", target_os = "ios",
-                       target_os = "dragonfly", target_os = "windows", target_env = "musl"),
-                   link_name = "je_nallocx")]
-        fn nallocx(size: size_t, flags: c_int) -> size_t;
     }
 
     const MALLOCX_ZERO: c_int = 0x40;
@@ -104,23 +94,16 @@ mod contents {
 
     #[no_mangle]
     #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_alloc(size: usize,
-                                     align: usize,
-                                     err: *mut u8) -> *mut u8 {
+    pub unsafe extern fn __rde_alloc(size: usize, align: usize) -> *mut u8 {
         let flags = align_to_flags(align, size);
         let ptr = mallocx(size as size_t, flags) as *mut u8;
-        if ptr.is_null() {
-            let layout = Layout::from_size_align_unchecked(size, align);
-            ptr::write(err as *mut AllocErr,
-                       AllocErr::Exhausted { request: layout });
-        }
         ptr
     }
 
     #[no_mangle]
     #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_oom(err: *const u8) -> ! {
-        System.oom((*(err as *const AllocErr)).clone())
+    pub unsafe extern fn __rde_oom() -> ! {
+        System.oom()
     }
 
     #[no_mangle]
@@ -134,116 +117,24 @@ mod contents {
 
     #[no_mangle]
     #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_usable_size(layout: *const u8,
-                                           min: *mut usize,
-                                           max: *mut usize) {
-        let layout = &*(layout as *const Layout);
-        let flags = align_to_flags(layout.align(), layout.size());
-        let size = nallocx(layout.size(), flags) as usize;
-        *min = layout.size();
-        if size > 0 {
-            *max = size;
-        } else {
-            *max = layout.size();
-        }
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
     pub unsafe extern fn __rde_realloc(ptr: *mut u8,
                                        _old_size: usize,
-                                       old_align: usize,
-                                       new_size: usize,
-                                       new_align: usize,
-                                       err: *mut u8) -> *mut u8 {
-        if new_align != old_align {
-            ptr::write(err as *mut AllocErr,
-                       AllocErr::Unsupported { details: "can't change alignments" });
-            return 0 as *mut u8
-        }
-
-        let flags = align_to_flags(new_align, new_size);
+                                       align: usize,
+                                       new_size: usize) -> *mut u8 {
+        let flags = align_to_flags(align, new_size);
         let ptr = rallocx(ptr as *mut c_void, new_size, flags) as *mut u8;
-        if ptr.is_null() {
-            let layout = Layout::from_size_align_unchecked(new_size, new_align);
-            ptr::write(err as *mut AllocErr,
-                       AllocErr::Exhausted { request: layout });
-        }
         ptr
     }
 
     #[no_mangle]
     #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_alloc_zeroed(size: usize,
-                                            align: usize,
-                                            err: *mut u8) -> *mut u8 {
+    pub unsafe extern fn __rde_alloc_zeroed(size: usize, align: usize) -> *mut u8 {
         let ptr = if align <= MIN_ALIGN && align <= size {
             calloc(size as size_t, 1) as *mut u8
         } else {
             let flags = align_to_flags(align, size) | MALLOCX_ZERO;
             mallocx(size as size_t, flags) as *mut u8
         };
-        if ptr.is_null() {
-            let layout = Layout::from_size_align_unchecked(size, align);
-            ptr::write(err as *mut AllocErr,
-                       AllocErr::Exhausted { request: layout });
-        }
         ptr
     }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_alloc_excess(size: usize,
-                                            align: usize,
-                                            excess: *mut usize,
-                                            err: *mut u8) -> *mut u8 {
-        let p = __rde_alloc(size, align, err);
-        if !p.is_null() {
-            let flags = align_to_flags(align, size);
-            *excess = nallocx(size, flags) as usize;
-        }
-        return p
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_realloc_excess(ptr: *mut u8,
-                                              old_size: usize,
-                                              old_align: usize,
-                                              new_size: usize,
-                                              new_align: usize,
-                                              excess: *mut usize,
-                                              err: *mut u8) -> *mut u8 {
-        let p = __rde_realloc(ptr, old_size, old_align, new_size, new_align, err);
-        if !p.is_null() {
-            let flags = align_to_flags(new_align, new_size);
-            *excess = nallocx(new_size, flags) as usize;
-        }
-        p
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_grow_in_place(ptr: *mut u8,
-                                             old_size: usize,
-                                             old_align: usize,
-                                             new_size: usize,
-                                             new_align: usize) -> u8 {
-        __rde_shrink_in_place(ptr, old_size, old_align, new_size, new_align)
-    }
-
-    #[no_mangle]
-    #[rustc_std_internal_symbol]
-    pub unsafe extern fn __rde_shrink_in_place(ptr: *mut u8,
-                                               _old_size: usize,
-                                               old_align: usize,
-                                               new_size: usize,
-                                               new_align: usize) -> u8 {
-        if old_align == new_align {
-            let flags = align_to_flags(new_align, new_size);
-            (xallocx(ptr as *mut c_void, new_size, 0, flags) == new_size) as u8
-        } else {
-            0
-        }
-    }
 }