Auto merge of #55660 - alexcrichton:cleanup-alloc-system, r=dtolnay,SimonSapin

Remove the `alloc_system` crate

In what's hopefully one of the final nails in the coffin of the "old allocator story of yore" this PR deletes the `alloc_system` crate and all traces of it from the compiler. The compiler no longer needs to inject allocator crates anywhere and the `alloc_system` crate has no real reason to exist outside the standard library.

The unstable `alloc_system` crate is folded directly into the standard library where its stable interface, the `System` type, remains the same. All unstable traces of `alloc_system` are removed, however.

9 files changed, 296 insertions, 0 deletions

diff --git a/src/libstd/sys/cloudabi/mod.rs b/src/libstd/sys/cloudabi/mod.rs
index 9e943c17fc8..dfb56472c6c 100644
--- a/src/libstd/sys/cloudabi/mod.rs
+++ b/src/libstd/sys/cloudabi/mod.rs
@@ -12,6 +12,8 @@ use io;
 use libc;
 use mem;
 
+#[path = "../unix/alloc.rs"]
+pub mod alloc;
 pub mod args;
 #[cfg(feature = "backtrace")]
 pub mod backtrace;
diff --git a/src/libstd/sys/redox/mod.rs b/src/libstd/sys/redox/mod.rs
index f943257c687..edb407ecd23 100644
--- a/src/libstd/sys/redox/mod.rs
+++ b/src/libstd/sys/redox/mod.rs
@@ -15,6 +15,8 @@ use io::{self, ErrorKind};
 pub use libc::strlen;
 pub use self::rand::hashmap_random_keys;
 
+#[path = "../unix/alloc.rs"]
+pub mod alloc;
 pub mod args;
 #[cfg(feature = "backtrace")]
 pub mod backtrace;
diff --git a/src/libstd/sys/unix/alloc.rs b/src/libstd/sys/unix/alloc.rs
new file mode 100644
index 00000000000..2a7f1934518
--- /dev/null
+++ b/src/libstd/sys/unix/alloc.rs
@@ -0,0 +1,100 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use ptr;
+use libc;
+use sys_common::alloc::{MIN_ALIGN, realloc_fallback};
+use alloc::{GlobalAlloc, Layout, System};
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
+            libc::malloc(layout.size()) as *mut u8
+        } else {
+            #[cfg(target_os = "macos")]
+            {
+                if layout.align() > (1 << 31) {
+                    return ptr::null_mut()
+                }
+            }
+            aligned_malloc(&layout)
+        }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
+            libc::calloc(layout.size(), 1) as *mut u8
+        } else {
+            let ptr = self.alloc(layout.clone());
+            if !ptr.is_null() {
+                ptr::write_bytes(ptr, 0, layout.size());
+            }
+            ptr
+        }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
+        libc::free(ptr as *mut libc::c_void)
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        if layout.align() <= MIN_ALIGN && layout.align() <= new_size {
+            libc::realloc(ptr as *mut libc::c_void, new_size) as *mut u8
+        } else {
+            realloc_fallback(self, ptr, layout, new_size)
+        }
+    }
+}
+
+#[cfg(any(target_os = "android",
+          target_os = "hermit",
+          target_os = "redox",
+          target_os = "solaris"))]
+#[inline]
+unsafe fn aligned_malloc(layout: &Layout) -> *mut u8 {
+    // On android we currently target API level 9 which unfortunately
+    // doesn't have the `posix_memalign` API used below. Instead we use
+    // `memalign`, but this unfortunately has the property on some systems
+    // where the memory returned cannot be deallocated by `free`!
+    //
+    // Upon closer inspection, however, this appears to work just fine with
+    // Android, so for this platform we should be fine to call `memalign`
+    // (which is present in API level 9). Some helpful references could
+    // possibly be chromium using memalign [1], attempts at documenting that
+    // memalign + free is ok [2] [3], or the current source of chromium
+    // which still uses memalign on android [4].
+    //
+    // [1]: https://codereview.chromium.org/10796020/
+    // [2]: https://code.google.com/p/android/issues/detail?id=35391
+    // [3]: https://bugs.chromium.org/p/chromium/issues/detail?id=138579
+    // [4]: https://chromium.googlesource.com/chromium/src/base/+/master/
+    //                                       /memory/aligned_memory.cc
+    libc::memalign(layout.align(), layout.size()) as *mut u8
+}
+
+#[cfg(not(any(target_os = "android",
+              target_os = "hermit",
+              target_os = "redox",
+              target_os = "solaris")))]
+#[inline]
+unsafe fn aligned_malloc(layout: &Layout) -> *mut u8 {
+    let mut out = ptr::null_mut();
+    let ret = libc::posix_memalign(&mut out, layout.align(), layout.size());
+    if ret != 0 {
+        ptr::null_mut()
+    } else {
+        out as *mut u8
+    }
+}
diff --git a/src/libstd/sys/unix/mod.rs b/src/libstd/sys/unix/mod.rs
index 17214be5b05..e8101bd0bc9 100644
--- a/src/libstd/sys/unix/mod.rs
+++ b/src/libstd/sys/unix/mod.rs
@@ -36,6 +36,7 @@ pub use libc::strlen;
 #[macro_use]
 pub mod weak;
 
+pub mod alloc;
 pub mod args;
 pub mod android;
 #[cfg(feature = "backtrace")]
diff --git a/src/libstd/sys/wasm/alloc.rs b/src/libstd/sys/wasm/alloc.rs
new file mode 100644
index 00000000000..0faa3c9a740
--- /dev/null
+++ b/src/libstd/sys/wasm/alloc.rs
@@ -0,0 +1,105 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! This is an implementation of a global allocator on the wasm32 platform when
+//! emscripten is not in use. In that situation there's no actual runtime for us
+//! to lean on for allocation, so instead we provide our own!
+//!
+//! The wasm32 instruction set has two instructions for getting the current
+//! amount of memory and growing the amount of memory. These instructions are the
+//! foundation on which we're able to build an allocator, so we do so! Note that
+//! the instructions are also pretty "global" and this is the "global" allocator
+//! after all!
+//!
+//! The current allocator here is the `dlmalloc` crate which we've got included
+//! in the rust-lang/rust repository as a submodule. The crate is a port of
+//! dlmalloc.c from C to Rust and is basically just so we can have "pure Rust"
+//! for now which is currently technically required (can't link with C yet).
+//!
+//! The crate itself provides a global allocator which on wasm has no
+//! synchronization as there are no threads!
+
+extern crate dlmalloc;
+
+use alloc::{GlobalAlloc, Layout, System};
+
+static mut DLMALLOC: dlmalloc::Dlmalloc = dlmalloc::DLMALLOC_INIT;
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        let _lock = lock::lock();
+        DLMALLOC.malloc(layout.size(), layout.align())
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        let _lock = lock::lock();
+        DLMALLOC.calloc(layout.size(), layout.align())
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        let _lock = lock::lock();
+        DLMALLOC.free(ptr, layout.size(), layout.align())
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        let _lock = lock::lock();
+        DLMALLOC.realloc(ptr, layout.size(), layout.align(), new_size)
+    }
+}
+
+#[cfg(target_feature = "atomics")]
+mod lock {
+    use arch::wasm32;
+    use sync::atomic::{AtomicI32, Ordering::SeqCst};
+
+    static LOCKED: AtomicI32 = AtomicI32::new(0);
+
+    pub struct DropLock;
+
+    pub fn lock() -> DropLock {
+        loop {
+            if LOCKED.swap(1, SeqCst) == 0 {
+                return DropLock
+            }
+            unsafe {
+                let r = wasm32::atomic::wait_i32(
+                    &LOCKED as *const AtomicI32 as *mut i32,
+                    1,  // expected value
+                    -1, // timeout
+                );
+                debug_assert!(r == 0 || r == 1);
+            }
+        }
+    }
+
+    impl Drop for DropLock {
+        fn drop(&mut self) {
+            let r = LOCKED.swap(0, SeqCst);
+            debug_assert_eq!(r, 1);
+            unsafe {
+                wasm32::atomic::wake(
+                    &LOCKED as *const AtomicI32 as *mut i32,
+                    1, // only one thread
+                );
+            }
+        }
+    }
+}
+
+#[cfg(not(target_feature = "atomics"))]
+mod lock {
+    #[inline]
+    pub fn lock() {} // no atomics, no threads, that's easy!
+}
diff --git a/src/libstd/sys/wasm/mod.rs b/src/libstd/sys/wasm/mod.rs
index e11b4d71aae..e8f7e32ac91 100644
--- a/src/libstd/sys/wasm/mod.rs
+++ b/src/libstd/sys/wasm/mod.rs
@@ -32,6 +32,7 @@ use sys_common::{AsInner, FromInner};
 use ffi::{OsString, OsStr};
 use time::Duration;
 
+pub mod alloc;
 pub mod args;
 #[cfg(feature = "backtrace")]
 pub mod backtrace;
diff --git a/src/libstd/sys/windows/alloc.rs b/src/libstd/sys/windows/alloc.rs
new file mode 100644
index 00000000000..e5de3e016c9
--- /dev/null
+++ b/src/libstd/sys/windows/alloc.rs
@@ -0,0 +1,77 @@
+// Copyright 2018 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+use alloc::{GlobalAlloc, Layout, System};
+use sys::c;
+use sys_common::alloc::{MIN_ALIGN, realloc_fallback};
+
+#[repr(C)]
+struct Header(*mut u8);
+
+unsafe fn get_header<'a>(ptr: *mut u8) -> &'a mut Header {
+    &mut *(ptr as *mut Header).offset(-1)
+}
+
+unsafe fn align_ptr(ptr: *mut u8, align: usize) -> *mut u8 {
+    let aligned = ptr.add(align - (ptr as usize & (align - 1)));
+    *get_header(aligned) = Header(ptr);
+    aligned
+}
+
+#[inline]
+unsafe fn allocate_with_flags(layout: Layout, flags: c::DWORD) -> *mut u8 {
+    if layout.align() <= MIN_ALIGN {
+        return c::HeapAlloc(c::GetProcessHeap(), flags, layout.size()) as *mut u8
+    }
+
+    let size = layout.size() + layout.align();
+    let ptr = c::HeapAlloc(c::GetProcessHeap(), flags, size);
+    if ptr.is_null() {
+        ptr as *mut u8
+    } else {
+        align_ptr(ptr as *mut u8, layout.align())
+    }
+}
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        allocate_with_flags(layout, 0)
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        allocate_with_flags(layout, c::HEAP_ZERO_MEMORY)
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        if layout.align() <= MIN_ALIGN {
+            let err = c::HeapFree(c::GetProcessHeap(), 0, ptr as c::LPVOID);
+            debug_assert!(err != 0, "Failed to free heap memory: {}",
+                          c::GetLastError());
+        } else {
+            let header = get_header(ptr);
+            let err = c::HeapFree(c::GetProcessHeap(), 0, header.0 as c::LPVOID);
+            debug_assert!(err != 0, "Failed to free heap memory: {}",
+                          c::GetLastError());
+        }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        if layout.align() <= MIN_ALIGN {
+            c::HeapReAlloc(c::GetProcessHeap(), 0, ptr as c::LPVOID, new_size) as *mut u8
+        } else {
+            realloc_fallback(self, ptr, layout, new_size)
+        }
+    }
+}
diff --git a/src/libstd/sys/windows/c.rs b/src/libstd/sys/windows/c.rs
index f4bd9c22bb9..c84874a3e88 100644
--- a/src/libstd/sys/windows/c.rs
+++ b/src/libstd/sys/windows/c.rs
@@ -309,6 +309,8 @@ pub const FD_SETSIZE: usize = 64;
 
 pub const STACK_SIZE_PARAM_IS_A_RESERVATION: DWORD = 0x00010000;
 
+pub const HEAP_ZERO_MEMORY: DWORD = 0x00000008;
+
 #[repr(C)]
 #[cfg(not(target_pointer_width = "64"))]
 pub struct WSADATA {
@@ -1277,6 +1279,11 @@ extern "system" {
 
     #[link_name = "SystemFunction036"]
     pub fn RtlGenRandom(RandomBuffer: *mut u8, RandomBufferLength: ULONG) -> BOOLEAN;
+
+    pub fn GetProcessHeap() -> HANDLE;
+    pub fn HeapAlloc(hHeap: HANDLE, dwFlags: DWORD, dwBytes: SIZE_T) -> LPVOID;
+    pub fn HeapReAlloc(hHeap: HANDLE, dwFlags: DWORD, lpMem: LPVOID, dwBytes: SIZE_T) -> LPVOID;
+    pub fn HeapFree(hHeap: HANDLE, dwFlags: DWORD, lpMem: LPVOID) -> BOOL;
 }
 
 // Functions that aren't available on every version of Windows that we support,
diff --git a/src/libstd/sys/windows/mod.rs b/src/libstd/sys/windows/mod.rs
index 31ef9fa2bed..f880bc8c050 100644
--- a/src/libstd/sys/windows/mod.rs
+++ b/src/libstd/sys/windows/mod.rs
@@ -22,6 +22,7 @@ pub use self::rand::hashmap_random_keys;
 
 #[macro_use] pub mod compat;
 
+pub mod alloc;
 pub mod args;
 #[cfg(feature = "backtrace")]
 pub mod backtrace;