std: move allocators to `sys`

11 files changed, 908 insertions, 0 deletions

diff --git a/library/std/src/sys/alloc/hermit.rs b/library/std/src/sys/alloc/hermit.rs
new file mode 100644
index 00000000000..77f8200a70a
--- /dev/null
+++ b/library/std/src/sys/alloc/hermit.rs
@@ -0,0 +1,27 @@
+use crate::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 {
+        let size = layout.size();
+        let align = layout.align();
+        unsafe { hermit_abi::malloc(size, align) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        let size = layout.size();
+        let align = layout.align();
+        unsafe {
+            hermit_abi::free(ptr, size, align);
+        }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        let size = layout.size();
+        let align = layout.align();
+        unsafe { hermit_abi::realloc(ptr, size, align, new_size) }
+    }
+}
diff --git a/library/std/src/sys/alloc/mod.rs b/library/std/src/sys/alloc/mod.rs
new file mode 100644
index 00000000000..2c0b533a570
--- /dev/null
+++ b/library/std/src/sys/alloc/mod.rs
@@ -0,0 +1,94 @@
+#![forbid(unsafe_op_in_unsafe_fn)]
+
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::ptr;
+
+// The minimum alignment guaranteed by the architecture. This value is used to
+// add fast paths for low alignment values.
+#[allow(dead_code)]
+const MIN_ALIGN: usize = if cfg!(any(
+    all(target_arch = "riscv32", any(target_os = "espidf", target_os = "zkvm")),
+    all(target_arch = "xtensa", target_os = "espidf"),
+)) {
+    // The allocator on the esp-idf and zkvm platforms guarantees 4 byte alignment.
+    4
+} else if cfg!(any(
+    target_arch = "x86",
+    target_arch = "arm",
+    target_arch = "m68k",
+    target_arch = "csky",
+    target_arch = "mips",
+    target_arch = "mips32r6",
+    target_arch = "powerpc",
+    target_arch = "powerpc64",
+    target_arch = "sparc",
+    target_arch = "wasm32",
+    target_arch = "hexagon",
+    target_arch = "riscv32",
+    target_arch = "xtensa",
+)) {
+    8
+} else if cfg!(any(
+    target_arch = "x86_64",
+    target_arch = "aarch64",
+    target_arch = "arm64ec",
+    target_arch = "loongarch64",
+    target_arch = "mips64",
+    target_arch = "mips64r6",
+    target_arch = "s390x",
+    target_arch = "sparc64",
+    target_arch = "riscv64",
+    target_arch = "wasm64",
+)) {
+    16
+} else {
+    panic!("add a value for MIN_ALIGN")
+};
+
+#[allow(dead_code)]
+unsafe fn realloc_fallback(
+    alloc: &System,
+    ptr: *mut u8,
+    old_layout: Layout,
+    new_size: usize,
+) -> *mut u8 {
+    // SAFETY: Docs for GlobalAlloc::realloc require this to be valid
+    unsafe {
+        let new_layout = Layout::from_size_align_unchecked(new_size, old_layout.align());
+
+        let new_ptr = GlobalAlloc::alloc(alloc, new_layout);
+        if !new_ptr.is_null() {
+            let size = usize::min(old_layout.size(), new_size);
+            ptr::copy_nonoverlapping(ptr, new_ptr, size);
+            GlobalAlloc::dealloc(alloc, ptr, old_layout);
+        }
+
+        new_ptr
+    }
+}
+
+cfg_if::cfg_if! {
+    if #[cfg(any(
+        target_family = "unix",
+        target_os = "wasi",
+        target_os = "teeos",
+    ))] {
+        mod unix;
+    } else if #[cfg(target_os = "windows")] {
+        mod windows;
+    } else if #[cfg(target_os = "hermit")] {
+        mod hermit;
+    } else if #[cfg(all(target_vendor = "fortanix", target_env = "sgx"))] {
+        mod sgx;
+    } else if #[cfg(target_os = "solid_asp3")] {
+        mod solid;
+    } else if #[cfg(target_os = "uefi")] {
+        mod uefi;
+    } else if #[cfg(target_family = "wasm")] {
+        mod wasm;
+    } else if #[cfg(target_os = "xous")] {
+        mod xous;
+    } else if #[cfg(target_os = "zkvm")] {
+        mod zkvm;
+    }
+}
diff --git a/library/std/src/sys/alloc/sgx.rs b/library/std/src/sys/alloc/sgx.rs
new file mode 100644
index 00000000000..fca9d087e5b
--- /dev/null
+++ b/library/std/src/sys/alloc/sgx.rs
@@ -0,0 +1,97 @@
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::ptr;
+use crate::sync::atomic::{AtomicBool, Ordering};
+use crate::sys::pal::abi::mem as sgx_mem;
+use crate::sys::pal::waitqueue::SpinMutex;
+
+// Using a SpinMutex because we never want to exit the enclave waiting for the
+// allocator.
+//
+// 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.
+#[cfg_attr(test, linkage = "available_externally")]
+#[export_name = "_ZN16__rust_internals3std3sys3sgx5alloc8DLMALLOCE"]
+static DLMALLOC: SpinMutex<dlmalloc::Dlmalloc<Sgx>> =
+    SpinMutex::new(dlmalloc::Dlmalloc::new_with_allocator(Sgx {}));
+
+struct Sgx;
+
+unsafe impl dlmalloc::Allocator for Sgx {
+    /// Allocs system resources
+    fn alloc(&self, _size: usize) -> (*mut u8, usize, u32) {
+        static INIT: AtomicBool = AtomicBool::new(false);
+
+        // No ordering requirement since this function is protected by the global lock.
+        if !INIT.swap(true, Ordering::Relaxed) {
+            (sgx_mem::heap_base() as _, sgx_mem::heap_size(), 0)
+        } else {
+            (ptr::null_mut(), 0, 0)
+        }
+    }
+
+    fn remap(&self, _ptr: *mut u8, _oldsize: usize, _newsize: usize, _can_move: bool) -> *mut u8 {
+        ptr::null_mut()
+    }
+
+    fn free_part(&self, _ptr: *mut u8, _oldsize: usize, _newsize: usize) -> bool {
+        false
+    }
+
+    fn free(&self, _ptr: *mut u8, _size: usize) -> bool {
+        return false;
+    }
+
+    fn can_release_part(&self, _flags: u32) -> bool {
+        false
+    }
+
+    fn allocates_zeros(&self) -> bool {
+        false
+    }
+
+    fn page_size(&self) -> usize {
+        0x1000
+    }
+}
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: the caller must uphold the safety contract for `malloc`
+        unsafe { DLMALLOC.lock().malloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: the caller must uphold the safety contract for `malloc`
+        unsafe { DLMALLOC.lock().calloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        // SAFETY: the caller must uphold the safety contract for `malloc`
+        unsafe { DLMALLOC.lock().free(ptr, layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        // SAFETY: the caller must uphold the safety contract for `malloc`
+        unsafe { DLMALLOC.lock().realloc(ptr, layout.size(), layout.align(), new_size) }
+    }
+}
+
+// The following functions are needed by libunwind. These symbols are named
+// in pre-link args for the target specification, so keep that in sync.
+#[cfg(not(test))]
+#[no_mangle]
+pub unsafe extern "C" fn __rust_c_alloc(size: usize, align: usize) -> *mut u8 {
+    unsafe { crate::alloc::alloc(Layout::from_size_align_unchecked(size, align)) }
+}
+
+#[cfg(not(test))]
+#[no_mangle]
+pub unsafe extern "C" fn __rust_c_dealloc(ptr: *mut u8, size: usize, align: usize) {
+    unsafe { crate::alloc::dealloc(ptr, Layout::from_size_align_unchecked(size, align)) }
+}
diff --git a/library/std/src/sys/alloc/solid.rs b/library/std/src/sys/alloc/solid.rs
new file mode 100644
index 00000000000..abb534a1c5c
--- /dev/null
+++ b/library/std/src/sys/alloc/solid.rs
@@ -0,0 +1,30 @@
+use super::{realloc_fallback, MIN_ALIGN};
+use crate::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() {
+            unsafe { libc::malloc(layout.size()) as *mut u8 }
+        } else {
+            unsafe { libc::memalign(layout.align(), layout.size()) as *mut u8 }
+        }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
+        unsafe { libc::free(ptr as *mut libc::c_void) }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        unsafe {
+            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)
+            }
+        }
+    }
+}
diff --git a/library/std/src/sys/alloc/uefi.rs b/library/std/src/sys/alloc/uefi.rs
new file mode 100644
index 00000000000..5221876e908
--- /dev/null
+++ b/library/std/src/sys/alloc/uefi.rs
@@ -0,0 +1,49 @@
+//! Global Allocator for UEFI.
+//! Uses [r-efi-alloc](https://crates.io/crates/r-efi-alloc)
+
+use r_efi::protocols::loaded_image;
+
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::sync::OnceLock;
+use crate::sys::pal::helpers;
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        static EFI_MEMORY_TYPE: OnceLock<u32> = OnceLock::new();
+
+        // Return null pointer if boot services are not available
+        if crate::os::uefi::env::boot_services().is_none() {
+            return crate::ptr::null_mut();
+        }
+
+        // If boot services is valid then SystemTable is not null.
+        let system_table = crate::os::uefi::env::system_table().as_ptr().cast();
+
+        // Each loaded image has an image handle that supports `EFI_LOADED_IMAGE_PROTOCOL`. Thus, this
+        // will never fail.
+        let mem_type = EFI_MEMORY_TYPE.get_or_init(|| {
+            let protocol = helpers::image_handle_protocol::<loaded_image::Protocol>(
+                loaded_image::PROTOCOL_GUID,
+            )
+            .unwrap();
+            // Gives allocations the memory type that the data sections were loaded as.
+            unsafe { (*protocol.as_ptr()).image_data_type }
+        });
+
+        // The caller must ensure non-0 layout
+        unsafe { r_efi_alloc::raw::alloc(system_table, layout, *mem_type) }
+    }
+
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        // Do nothing if boot services are not available
+        if crate::os::uefi::env::boot_services().is_none() {
+            return;
+        }
+
+        // If boot services is valid then SystemTable is not null.
+        let system_table = crate::os::uefi::env::system_table().as_ptr().cast();
+        // The caller must ensure non-0 layout
+        unsafe { r_efi_alloc::raw::dealloc(system_table, ptr, layout) }
+    }
+}
diff --git a/library/std/src/sys/alloc/unix.rs b/library/std/src/sys/alloc/unix.rs
new file mode 100644
index 00000000000..46ed7de7162
--- /dev/null
+++ b/library/std/src/sys/alloc/unix.rs
@@ -0,0 +1,88 @@
+use super::{realloc_fallback, MIN_ALIGN};
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::ptr;
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        // jemalloc provides alignment less than MIN_ALIGN for small allocations.
+        // So only rely on MIN_ALIGN if size >= align.
+        // Also see <https://github.com/rust-lang/rust/issues/45955> and
+        // <https://github.com/rust-lang/rust/issues/62251#issuecomment-507580914>.
+        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
+            unsafe { libc::malloc(layout.size()) as *mut u8 }
+        } else {
+            // `posix_memalign` returns a non-aligned value if supplied a very
+            // large alignment on older versions of Apple's platforms (unknown
+            // exactly which version range, but the issue is definitely
+            // present in macOS 10.14 and iOS 13.3).
+            //
+            // <https://github.com/rust-lang/rust/issues/30170>
+            #[cfg(target_vendor = "apple")]
+            {
+                if layout.align() > (1 << 31) {
+                    return ptr::null_mut();
+                }
+            }
+            unsafe { aligned_malloc(&layout) }
+        }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        // See the comment above in `alloc` for why this check looks the way it does.
+        if layout.align() <= MIN_ALIGN && layout.align() <= layout.size() {
+            unsafe { libc::calloc(layout.size(), 1) as *mut u8 }
+        } else {
+            let ptr = unsafe { self.alloc(layout) };
+            if !ptr.is_null() {
+                unsafe { ptr::write_bytes(ptr, 0, layout.size()) };
+            }
+            ptr
+        }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) {
+        unsafe { 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 {
+            unsafe { libc::realloc(ptr as *mut libc::c_void, new_size) as *mut u8 }
+        } else {
+            unsafe { realloc_fallback(self, ptr, layout, new_size) }
+        }
+    }
+}
+
+cfg_if::cfg_if! {
+    // We use posix_memalign wherever possible, but some targets have very incomplete POSIX coverage
+    // so we need a fallback for those.
+    if #[cfg(any(
+        target_os = "horizon",
+        target_os = "vita",
+    ))] {
+        #[inline]
+        unsafe fn aligned_malloc(layout: &Layout) -> *mut u8 {
+            unsafe { libc::memalign(layout.align(), layout.size()) as *mut u8 }
+        }
+    } else {
+        #[inline]
+        unsafe fn aligned_malloc(layout: &Layout) -> *mut u8 {
+            let mut out = ptr::null_mut();
+            // We prefer posix_memalign over aligned_alloc since it is more widely available, and
+            // since with aligned_alloc, implementations are making almost arbitrary choices for
+            // which alignments are "supported", making it hard to use. For instance, some
+            // implementations require the size to be a multiple of the alignment (wasi emmalloc),
+            // while others require the alignment to be at least the pointer size (Illumos, macOS).
+            // posix_memalign only has one, clear requirement: that the alignment be a multiple of
+            // `sizeof(void*)`. Since these are all powers of 2, we can just use max.
+            let align = layout.align().max(crate::mem::size_of::<usize>());
+            let ret = unsafe { libc::posix_memalign(&mut out, align, layout.size()) };
+            if ret != 0 { ptr::null_mut() } else { out as *mut u8 }
+        }
+    }
+}
diff --git a/library/std/src/sys/alloc/wasm.rs b/library/std/src/sys/alloc/wasm.rs
new file mode 100644
index 00000000000..ef9d753d7f8
--- /dev/null
+++ b/library/std/src/sys/alloc/wasm.rs
@@ -0,0 +1,167 @@
+//! This is an implementation of a global allocator on wasm targets 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 wasm 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!
+
+use crate::alloc::{GlobalAlloc, Layout, System};
+
+static mut DLMALLOC: dlmalloc::Dlmalloc = dlmalloc::Dlmalloc::new();
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling malloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.malloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling calloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.calloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling free() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.free(ptr, layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling realloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.realloc(ptr, layout.size(), layout.align(), new_size) }
+    }
+}
+
+#[cfg(target_feature = "atomics")]
+mod lock {
+    use crate::sync::atomic::AtomicI32;
+    use crate::sync::atomic::Ordering::{Acquire, Release};
+
+    static LOCKED: AtomicI32 = AtomicI32::new(0);
+
+    pub struct DropLock;
+
+    pub fn lock() -> DropLock {
+        loop {
+            if LOCKED.swap(1, Acquire) == 0 {
+                return DropLock;
+            }
+            // Ok so here's where things get a little depressing. At this point
+            // in time we need to synchronously acquire a lock, but we're
+            // contending with some other thread. Typically we'd execute some
+            // form of `i32.atomic.wait` like so:
+            //
+            //     unsafe {
+            //         let r = core::arch::wasm32::i32_atomic_wait(
+            //             LOCKED.as_mut_ptr(),
+            //             1,  //     expected value
+            //             -1, //     timeout
+            //         );
+            //         debug_assert!(r == 0 || r == 1);
+            //     }
+            //
+            // Unfortunately though in doing so we would cause issues for the
+            // main thread. The main thread in a web browser *cannot ever
+            // block*, no exceptions. This means that the main thread can't
+            // actually execute the `i32.atomic.wait` instruction.
+            //
+            // As a result if we want to work within the context of browsers we
+            // need to figure out some sort of allocation scheme for the main
+            // thread where when there's contention on the global malloc lock we
+            // do... something.
+            //
+            // Possible ideas include:
+            //
+            // 1. Attempt to acquire the global lock. If it fails, fall back to
+            //    memory allocation via `memory.grow`. Later just ... somehow
+            //    ... inject this raw page back into the main allocator as it
+            //    gets sliced up over time. This strategy has the downside of
+            //    forcing allocation of a page to happen whenever the main
+            //    thread contents with other threads, which is unfortunate.
+            //
+            // 2. Maintain a form of "two level" allocator scheme where the main
+            //    thread has its own allocator. Somehow this allocator would
+            //    also be balanced with a global allocator, not only to have
+            //    allocations cross between threads but also to ensure that the
+            //    two allocators stay "balanced" in terms of free'd memory and
+            //    such. This, however, seems significantly complicated.
+            //
+            // Out of a lack of other ideas, the current strategy implemented
+            // here is to simply spin. Typical spin loop algorithms have some
+            // form of "hint" here to the CPU that it's what we're doing to
+            // ensure that the CPU doesn't get too hot, but wasm doesn't have
+            // such an instruction.
+            //
+            // To be clear, spinning here is not a great solution.
+            // Another thread with the lock may take quite a long time to wake
+            // up. For example it could be in `memory.grow` or it could be
+            // evicted from the CPU for a timeslice like 10ms. For these periods
+            // of time our thread will "helpfully" sit here and eat CPU time
+            // until it itself is evicted or the lock holder finishes. This
+            // means we're just burning and wasting CPU time to no one's
+            // benefit.
+            //
+            // Spinning does have the nice properties, though, of being
+            // semantically correct, being fair to all threads for memory
+            // allocation, and being simple enough to implement.
+            //
+            // This will surely (hopefully) be replaced in the future with a
+            // real memory allocator that can handle the restriction of the main
+            // thread.
+            //
+            //
+            // FIXME: We can also possibly add an optimization here to detect
+            // when a thread is the main thread or not and block on all
+            // non-main-thread threads. Currently, however, we have no way
+            // of knowing which wasm thread is on the browser main thread, but
+            // if we could figure out we could at least somewhat mitigate the
+            // cost of this spinning.
+        }
+    }
+
+    impl Drop for DropLock {
+        fn drop(&mut self) {
+            let r = LOCKED.swap(0, Release);
+            debug_assert_eq!(r, 1);
+
+            // Note that due to the above logic we don't actually need to wake
+            // anyone up, but if we did it'd likely look something like this:
+            //
+            //     unsafe {
+            //         core::arch::wasm32::atomic_notify(
+            //             LOCKED.as_mut_ptr(),
+            //             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/library/std/src/sys/alloc/windows.rs b/library/std/src/sys/alloc/windows.rs
new file mode 100644
index 00000000000..e91956966aa
--- /dev/null
+++ b/library/std/src/sys/alloc/windows.rs
@@ -0,0 +1,261 @@
+use super::{realloc_fallback, MIN_ALIGN};
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::ffi::c_void;
+use crate::mem::MaybeUninit;
+use crate::ptr;
+use crate::sync::atomic::{AtomicPtr, Ordering};
+use crate::sys::c;
+
+#[cfg(test)]
+mod tests;
+
+// Heap memory management on Windows is done by using the system Heap API (heapapi.h)
+// See https://docs.microsoft.com/windows/win32/api/heapapi/
+
+// Flag to indicate that the memory returned by `HeapAlloc` should be zeroed.
+const HEAP_ZERO_MEMORY: u32 = 0x00000008;
+
+// Get a handle to the default heap of the current process, or null if the operation fails.
+//
+// SAFETY: Successful calls to this function within the same process are assumed to
+// always return the same handle, which remains valid for the entire lifetime of the process.
+//
+// See https://docs.microsoft.com/windows/win32/api/heapapi/nf-heapapi-getprocessheap
+windows_targets::link!("kernel32.dll" "system" fn GetProcessHeap() -> c::HANDLE);
+
+// Allocate a block of `dwBytes` bytes of memory from a given heap `hHeap`.
+// The allocated memory may be uninitialized, or zeroed if `dwFlags` is
+// set to `HEAP_ZERO_MEMORY`.
+//
+// Returns a pointer to the newly-allocated memory or null if the operation fails.
+// The returned pointer will be aligned to at least `MIN_ALIGN`.
+//
+// SAFETY:
+//  - `hHeap` must be a non-null handle returned by `GetProcessHeap`.
+//  - `dwFlags` must be set to either zero or `HEAP_ZERO_MEMORY`.
+//
+// Note that `dwBytes` is allowed to be zero, contrary to some other allocators.
+//
+// See https://docs.microsoft.com/windows/win32/api/heapapi/nf-heapapi-heapalloc
+windows_targets::link!("kernel32.dll" "system" fn HeapAlloc(hheap: c::HANDLE, dwflags: u32, dwbytes: usize) -> *mut c_void);
+
+// Reallocate a block of memory behind a given pointer `lpMem` from a given heap `hHeap`,
+// to a block of at least `dwBytes` bytes, either shrinking the block in place,
+// or allocating at a new location, copying memory, and freeing the original location.
+//
+// Returns a pointer to the reallocated memory or null if the operation fails.
+// The returned pointer will be aligned to at least `MIN_ALIGN`.
+// If the operation fails the given block will never have been freed.
+//
+// SAFETY:
+//  - `hHeap` must be a non-null handle returned by `GetProcessHeap`.
+//  - `dwFlags` must be set to zero.
+//  - `lpMem` must be a non-null pointer to an allocated block returned by `HeapAlloc` or
+//     `HeapReAlloc`, that has not already been freed.
+// If the block was successfully reallocated at a new location, pointers pointing to
+// the freed memory, such as `lpMem`, must not be dereferenced ever again.
+//
+// Note that `dwBytes` is allowed to be zero, contrary to some other allocators.
+//
+// See https://docs.microsoft.com/windows/win32/api/heapapi/nf-heapapi-heaprealloc
+windows_targets::link!("kernel32.dll" "system" fn HeapReAlloc(
+    hheap: c::HANDLE,
+    dwflags : u32,
+    lpmem: *const c_void,
+    dwbytes: usize
+) -> *mut c_void);
+
+// Free a block of memory behind a given pointer `lpMem` from a given heap `hHeap`.
+// Returns a nonzero value if the operation is successful, and zero if the operation fails.
+//
+// SAFETY:
+//  - `hHeap` must be a non-null handle returned by `GetProcessHeap`.
+//  - `dwFlags` must be set to zero.
+//  - `lpMem` must be a pointer to an allocated block returned by `HeapAlloc` or `HeapReAlloc`,
+//     that has not already been freed.
+// If the block was successfully freed, pointers pointing to the freed memory, such as `lpMem`,
+// must not be dereferenced ever again.
+//
+// Note that `lpMem` is allowed to be null, which will not cause the operation to fail.
+//
+// See https://docs.microsoft.com/windows/win32/api/heapapi/nf-heapapi-heapfree
+windows_targets::link!("kernel32.dll" "system" fn HeapFree(hheap: c::HANDLE, dwflags: u32, lpmem: *const c_void) -> c::BOOL);
+
+// Cached handle to the default heap of the current process.
+// Either a non-null handle returned by `GetProcessHeap`, or null when not yet initialized or `GetProcessHeap` failed.
+static HEAP: AtomicPtr<c_void> = AtomicPtr::new(ptr::null_mut());
+
+// Get a handle to the default heap of the current process, or null if the operation fails.
+// If this operation is successful, `HEAP` will be successfully initialized and contain
+// a non-null handle returned by `GetProcessHeap`.
+#[inline]
+fn init_or_get_process_heap() -> c::HANDLE {
+    // `HEAP` has not yet been successfully initialized
+    let heap = unsafe { GetProcessHeap() };
+    if !heap.is_null() {
+        // SAFETY: No locking is needed because within the same process,
+        // successful calls to `GetProcessHeap` will always return the same value, even on different threads.
+        HEAP.store(heap, Ordering::Release);
+
+        // SAFETY: `HEAP` contains a non-null handle returned by `GetProcessHeap`
+        heap
+    } else {
+        // Could not get the current process heap.
+        ptr::null_mut()
+    }
+}
+
+/// This is outlined from `process_heap_alloc` so that `process_heap_alloc`
+/// does not need any stack allocations.
+#[inline(never)]
+#[cold]
+extern "C" fn process_heap_init_and_alloc(
+    _heap: MaybeUninit<c::HANDLE>, // We pass this argument to match the ABI of `HeapAlloc`
+    flags: u32,
+    bytes: usize,
+) -> *mut c_void {
+    let heap = init_or_get_process_heap();
+    if core::intrinsics::unlikely(heap.is_null()) {
+        return ptr::null_mut();
+    }
+    // SAFETY: `heap` is a non-null handle returned by `GetProcessHeap`.
+    unsafe { HeapAlloc(heap, flags, bytes) }
+}
+
+#[inline(never)]
+fn process_heap_alloc(
+    _heap: MaybeUninit<c::HANDLE>, // We pass this argument to match the ABI of `HeapAlloc`,
+    flags: u32,
+    bytes: usize,
+) -> *mut c_void {
+    let heap = HEAP.load(Ordering::Relaxed);
+    if core::intrinsics::likely(!heap.is_null()) {
+        // SAFETY: `heap` is a non-null handle returned by `GetProcessHeap`.
+        unsafe { HeapAlloc(heap, flags, bytes) }
+    } else {
+        process_heap_init_and_alloc(MaybeUninit::uninit(), flags, bytes)
+    }
+}
+
+// Get a non-null handle to the default heap of the current process.
+// SAFETY: `HEAP` must have been successfully initialized.
+#[inline]
+unsafe fn get_process_heap() -> c::HANDLE {
+    HEAP.load(Ordering::Acquire)
+}
+
+// Header containing a pointer to the start of an allocated block.
+// SAFETY: Size and alignment must be <= `MIN_ALIGN`.
+#[repr(C)]
+struct Header(*mut u8);
+
+// Allocate a block of optionally zeroed memory for a given `layout`.
+// SAFETY: Returns a pointer satisfying the guarantees of `System` about allocated pointers,
+// or null if the operation fails. If this returns non-null `HEAP` will have been successfully
+// initialized.
+#[inline]
+unsafe fn allocate(layout: Layout, zeroed: bool) -> *mut u8 {
+    // Allocated memory will be either zeroed or uninitialized.
+    let flags = if zeroed { HEAP_ZERO_MEMORY } else { 0 };
+
+    if layout.align() <= MIN_ALIGN {
+        // The returned pointer points to the start of an allocated block.
+        process_heap_alloc(MaybeUninit::uninit(), flags, layout.size()) as *mut u8
+    } else {
+        // Allocate extra padding in order to be able to satisfy the alignment.
+        let total = layout.align() + layout.size();
+
+        let ptr = process_heap_alloc(MaybeUninit::uninit(), flags, total) as *mut u8;
+        if ptr.is_null() {
+            // Allocation has failed.
+            return ptr::null_mut();
+        }
+
+        // Create a correctly aligned pointer offset from the start of the allocated block,
+        // and write a header before it.
+
+        let offset = layout.align() - (ptr.addr() & (layout.align() - 1));
+        // SAFETY: `MIN_ALIGN` <= `offset` <= `layout.align()` and the size of the allocated
+        // block is `layout.align() + layout.size()`. `aligned` will thus be a correctly aligned
+        // pointer inside the allocated block with at least `layout.size()` bytes after it and at
+        // least `MIN_ALIGN` bytes of padding before it.
+        let aligned = unsafe { ptr.add(offset) };
+        // SAFETY: Because the size and alignment of a header is <= `MIN_ALIGN` and `aligned`
+        // is aligned to at least `MIN_ALIGN` and has at least `MIN_ALIGN` bytes of padding before
+        // it, it is safe to write a header directly before it.
+        unsafe { ptr::write((aligned as *mut Header).sub(1), Header(ptr)) };
+
+        // SAFETY: The returned pointer does not point to the start of an allocated block,
+        // but there is a header readable directly before it containing the location of the start
+        // of the block.
+        aligned
+    }
+}
+
+// All pointers returned by this allocator have, in addition to the guarantees of `GlobalAlloc`, the
+// following properties:
+//
+// If the pointer was allocated or reallocated with a `layout` specifying an alignment <= `MIN_ALIGN`
+// the pointer will be aligned to at least `MIN_ALIGN` and point to the start of the allocated block.
+//
+// If the pointer was allocated or reallocated with a `layout` specifying an alignment > `MIN_ALIGN`
+// the pointer will be aligned to the specified alignment and not point to the start of the allocated block.
+// Instead there will be a header readable directly before the returned pointer, containing the actual
+// location of the start of the block.
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: Pointers returned by `allocate` satisfy the guarantees of `System`
+        let zeroed = false;
+        unsafe { allocate(layout, zeroed) }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: Pointers returned by `allocate` satisfy the guarantees of `System`
+        let zeroed = true;
+        unsafe { allocate(layout, zeroed) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        let block = {
+            if layout.align() <= MIN_ALIGN {
+                ptr
+            } else {
+                // The location of the start of the block is stored in the padding before `ptr`.
+
+                // SAFETY: Because of the contract of `System`, `ptr` is guaranteed to be non-null
+                // and have a header readable directly before it.
+                unsafe { ptr::read((ptr as *mut Header).sub(1)).0 }
+            }
+        };
+
+        // SAFETY: because `ptr` has been successfully allocated with this allocator,
+        // `HEAP` must have been successfully initialized.
+        let heap = unsafe { get_process_heap() };
+
+        // SAFETY: `heap` is a non-null handle returned by `GetProcessHeap`,
+        // `block` is a pointer to the start of an allocated block.
+        unsafe { HeapFree(heap, 0, block.cast::<c_void>()) };
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        if layout.align() <= MIN_ALIGN {
+            // SAFETY: because `ptr` has been successfully allocated with this allocator,
+            // `HEAP` must have been successfully initialized.
+            let heap = unsafe { get_process_heap() };
+
+            // SAFETY: `heap` is a non-null handle returned by `GetProcessHeap`,
+            // `ptr` is a pointer to the start of an allocated block.
+            // The returned pointer points to the start of an allocated block.
+            unsafe { HeapReAlloc(heap, 0, ptr.cast::<c_void>(), new_size).cast::<u8>() }
+        } else {
+            // SAFETY: `realloc_fallback` is implemented using `dealloc` and `alloc`, which will
+            // correctly handle `ptr` and return a pointer satisfying the guarantees of `System`
+            unsafe { realloc_fallback(self, ptr, layout, new_size) }
+        }
+    }
+}
diff --git a/library/std/src/sys/alloc/windows/tests.rs b/library/std/src/sys/alloc/windows/tests.rs
new file mode 100644
index 00000000000..674a3e1d92d
--- /dev/null
+++ b/library/std/src/sys/alloc/windows/tests.rs
@@ -0,0 +1,9 @@
+use super::{Header, MIN_ALIGN};
+use crate::mem;
+
+#[test]
+fn alloc_header() {
+    // Header must fit in the padding before an aligned pointer
+    assert!(mem::size_of::<Header>() <= MIN_ALIGN);
+    assert!(mem::align_of::<Header>() <= MIN_ALIGN);
+}
diff --git a/library/std/src/sys/alloc/xous.rs b/library/std/src/sys/alloc/xous.rs
new file mode 100644
index 00000000000..9ea43445d02
--- /dev/null
+++ b/library/std/src/sys/alloc/xous.rs
@@ -0,0 +1,71 @@
+use crate::alloc::{GlobalAlloc, Layout, System};
+
+#[cfg(not(test))]
+#[export_name = "_ZN16__rust_internals3std3sys4xous5alloc8DLMALLOCE"]
+static mut DLMALLOC: dlmalloc::Dlmalloc = dlmalloc::Dlmalloc::new();
+
+#[cfg(test)]
+extern "Rust" {
+    #[link_name = "_ZN16__rust_internals3std3sys4xous5alloc8DLMALLOCE"]
+    static mut DLMALLOC: dlmalloc::Dlmalloc;
+}
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling malloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.malloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling calloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.calloc(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling free() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.free(ptr, layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 {
+        // SAFETY: DLMALLOC access is guaranteed to be safe because the lock gives us unique and non-reentrant access.
+        // Calling realloc() is safe because preconditions on this function match the trait method preconditions.
+        let _lock = lock::lock();
+        unsafe { DLMALLOC.realloc(ptr, layout.size(), layout.align(), new_size) }
+    }
+}
+
+mod lock {
+    use crate::sync::atomic::AtomicI32;
+    use crate::sync::atomic::Ordering::{Acquire, Release};
+
+    static LOCKED: AtomicI32 = AtomicI32::new(0);
+
+    pub struct DropLock;
+
+    pub fn lock() -> DropLock {
+        loop {
+            if LOCKED.swap(1, Acquire) == 0 {
+                return DropLock;
+            }
+            crate::os::xous::ffi::do_yield();
+        }
+    }
+
+    impl Drop for DropLock {
+        fn drop(&mut self) {
+            let r = LOCKED.swap(0, Release);
+            debug_assert_eq!(r, 1);
+        }
+    }
+}
diff --git a/library/std/src/sys/alloc/zkvm.rs b/library/std/src/sys/alloc/zkvm.rs
new file mode 100644
index 00000000000..a600cfa2220
--- /dev/null
+++ b/library/std/src/sys/alloc/zkvm.rs
@@ -0,0 +1,15 @@
+use crate::alloc::{GlobalAlloc, Layout, System};
+use crate::sys::pal::abi;
+
+#[stable(feature = "alloc_system_type", since = "1.28.0")]
+unsafe impl GlobalAlloc for System {
+    #[inline]
+    unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
+        unsafe { abi::sys_alloc_aligned(layout.size(), layout.align()) }
+    }
+
+    #[inline]
+    unsafe fn dealloc(&self, _ptr: *mut u8, _layout: Layout) {
+        // this allocator never deallocates memory
+    }
+}