std: Refactor liballoc out of lib{std,sync}

This commit is part of the libstd facade RFC, issue #13851. This creates a new
library, liballoc, which is intended to be the core allocation library for all
of Rust. It is pinned on the basic assumption that an allocation failure is an
abort or failure.

This module has inherited the heap/libc_heap modules from std::rt, the owned/rc
modules from std, and the arc module from libsync. These three pointers are
currently the three most core pointer implementations in Rust.

The UnsafeArc type in std::sync should be considered deprecated and replaced by
Arc<Unsafe<T>>. This commit does not currently migrate to this type, but future
commits will continue this refactoring.

7 files changed, 1201 insertions, 0 deletions

diff --git a/src/liballoc/arc.rs b/src/liballoc/arc.rs
new file mode 100644
index 00000000000..1ad79072e75
--- /dev/null
+++ b/src/liballoc/arc.rs
@@ -0,0 +1,400 @@
+// Copyright 2012-2014 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.
+
+/*!
+ * Concurrency-enabled mechanisms for sharing mutable and/or immutable state
+ * between tasks.
+ */
+
+use core::atomics;
+use core::clone::Clone;
+use core::kinds::{Share, Send};
+use core::mem::{min_align_of, size_of, drop};
+use core::mem;
+use core::ops::{Drop, Deref};
+use core::option::{Some, None, Option};
+use core::ptr;
+use core::ptr::RawPtr;
+use heap::deallocate;
+
+/// An atomically reference counted wrapper for shared state.
+///
+/// # Example
+///
+/// In this example, a large vector of floats is shared between several tasks.
+/// With simple pipes, without `Arc`, a copy would have to be made for each
+/// task.
+///
+/// ```rust
+/// extern crate sync;
+///
+/// use sync::Arc;
+///
+/// fn main() {
+///     let numbers = Vec::from_fn(100, |i| i as f32);
+///     let shared_numbers = Arc::new(numbers);
+///
+///     for _ in range(0, 10) {
+///         let child_numbers = shared_numbers.clone();
+///
+///         spawn(proc() {
+///             let local_numbers = child_numbers.as_slice();
+///
+///             // Work with the local numbers
+///         });
+///     }
+/// }
+/// ```
+#[unsafe_no_drop_flag]
+pub struct Arc<T> {
+    x: *mut ArcInner<T>,
+}
+
+/// A weak pointer to an `Arc`.
+///
+/// Weak pointers will not keep the data inside of the `Arc` alive, and can be
+/// used to break cycles between `Arc` pointers.
+#[unsafe_no_drop_flag]
+pub struct Weak<T> {
+    x: *mut ArcInner<T>,
+}
+
+struct ArcInner<T> {
+    strong: atomics::AtomicUint,
+    weak: atomics::AtomicUint,
+    data: T,
+}
+
+impl<T: Share + Send> Arc<T> {
+    /// Create an atomically reference counted wrapper.
+    #[inline]
+    pub fn new(data: T) -> Arc<T> {
+        // Start the weak pointer count as 1 which is the weak pointer that's
+        // held by all the strong pointers (kinda), see std/rc.rs for more info
+        let x = box ArcInner {
+            strong: atomics::AtomicUint::new(1),
+            weak: atomics::AtomicUint::new(1),
+            data: data,
+        };
+        Arc { x: unsafe { mem::transmute(x) } }
+    }
+
+    #[inline]
+    fn inner<'a>(&'a self) -> &'a ArcInner<T> {
+        // This unsafety is ok because while this arc is alive we're guaranteed
+        // that the inner pointer is valid. Furthermore, we know that the
+        // `ArcInner` structure itself is `Share` because the inner data is
+        // `Share` as well, so we're ok loaning out an immutable pointer to
+        // these contents.
+        unsafe { &*self.x }
+    }
+
+    /// Downgrades a strong pointer to a weak pointer
+    ///
+    /// Weak pointers will not keep the data alive. Once all strong references
+    /// to the underlying data have been dropped, the data itself will be
+    /// destroyed.
+    pub fn downgrade(&self) -> Weak<T> {
+        // See the clone() impl for why this is relaxed
+        self.inner().weak.fetch_add(1, atomics::Relaxed);
+        Weak { x: self.x }
+    }
+}
+
+impl<T: Share + Send> Clone for Arc<T> {
+    /// Duplicate an atomically reference counted wrapper.
+    ///
+    /// The resulting two `Arc` objects will point to the same underlying data
+    /// object. However, one of the `Arc` objects can be sent to another task,
+    /// allowing them to share the underlying data.
+    #[inline]
+    fn clone(&self) -> Arc<T> {
+        // Using a relaxed ordering is alright here, as knowledge of the
+        // original reference prevents other threads from erroneously deleting
+        // the object.
+        //
+        // As explained in the [Boost documentation][1], Increasing the
+        // reference counter can always be done with memory_order_relaxed: New
+        // references to an object can only be formed from an existing
+        // reference, and passing an existing reference from one thread to
+        // another must already provide any required synchronization.
+        //
+        // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+        self.inner().strong.fetch_add(1, atomics::Relaxed);
+        Arc { x: self.x }
+    }
+}
+
+impl<T: Send + Share> Deref<T> for Arc<T> {
+    #[inline]
+    fn deref<'a>(&'a self) -> &'a T {
+        &self.inner().data
+    }
+}
+
+impl<T: Send + Share + Clone> Arc<T> {
+    /// Acquires a mutable pointer to the inner contents by guaranteeing that
+    /// the reference count is one (no sharing is possible).
+    ///
+    /// This is also referred to as a copy-on-write operation because the inner
+    /// data is cloned if the reference count is greater than one.
+    #[inline]
+    #[experimental]
+    pub fn make_unique<'a>(&'a mut self) -> &'a mut T {
+        if self.inner().strong.load(atomics::SeqCst) != 1 {
+            *self = Arc::new(self.deref().clone())
+        }
+        // This unsafety is ok because we're guaranteed that the pointer
+        // returned is the *only* pointer that will ever be returned to T. Our
+        // reference count is guaranteed to be 1 at this point, and we required
+        // the Arc itself to be `mut`, so we're returning the only possible
+        // reference to the inner data.
+        unsafe { mem::transmute::<&_, &mut _>(self.deref()) }
+    }
+}
+
+#[unsafe_destructor]
+impl<T: Share + Send> Drop for Arc<T> {
+    fn drop(&mut self) {
+        // This structure has #[unsafe_no_drop_flag], so this drop glue may run
+        // more than once (but it is guaranteed to be zeroed after the first if
+        // it's run more than once)
+        if self.x.is_null() { return }
+
+        // Because `fetch_sub` is already atomic, we do not need to synchronize
+        // with other threads unless we are going to delete the object. This
+        // same logic applies to the below `fetch_sub` to the `weak` count.
+        if self.inner().strong.fetch_sub(1, atomics::Release) != 1 { return }
+
+        // This fence is needed to prevent reordering of use of the data and
+        // deletion of the data. Because it is marked `Release`, the
+        // decreasing of the reference count sychronizes with this `Acquire`
+        // fence. This means that use of the data happens before decreasing
+        // the refernce count, which happens before this fence, which
+        // happens before the deletion of the data.
+        //
+        // As explained in the [Boost documentation][1],
+        //
+        // It is important to enforce any possible access to the object in
+        // one thread (through an existing reference) to *happen before*
+        // deleting the object in a different thread. This is achieved by a
+        // "release" operation after dropping a reference (any access to the
+        // object through this reference must obviously happened before),
+        // and an "acquire" operation before deleting the object.
+        //
+        // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+        atomics::fence(atomics::Acquire);
+
+        // Destroy the data at this time, even though we may not free the box
+        // allocation itself (there may still be weak pointers lying around).
+        unsafe { drop(ptr::read(&self.inner().data)); }
+
+        if self.inner().weak.fetch_sub(1, atomics::Release) == 1 {
+            atomics::fence(atomics::Acquire);
+            unsafe { deallocate(self.x as *mut u8, size_of::<ArcInner<T>>(),
+                                min_align_of::<ArcInner<T>>()) }
+        }
+    }
+}
+
+impl<T: Share + Send> Weak<T> {
+    /// Attempts to upgrade this weak reference to a strong reference.
+    ///
+    /// This method will fail to upgrade this reference if the strong reference
+    /// count has already reached 0, but if there are still other active strong
+    /// references this function will return a new strong reference to the data
+    pub fn upgrade(&self) -> Option<Arc<T>> {
+        // We use a CAS loop to increment the strong count instead of a
+        // fetch_add because once the count hits 0 is must never be above 0.
+        let inner = self.inner();
+        loop {
+            let n = inner.strong.load(atomics::SeqCst);
+            if n == 0 { return None }
+            let old = inner.strong.compare_and_swap(n, n + 1, atomics::SeqCst);
+            if old == n { return Some(Arc { x: self.x }) }
+        }
+    }
+
+    #[inline]
+    fn inner<'a>(&'a self) -> &'a ArcInner<T> {
+        // See comments above for why this is "safe"
+        unsafe { &*self.x }
+    }
+}
+
+impl<T: Share + Send> Clone for Weak<T> {
+    #[inline]
+    fn clone(&self) -> Weak<T> {
+        // See comments in Arc::clone() for why this is relaxed
+        self.inner().weak.fetch_add(1, atomics::Relaxed);
+        Weak { x: self.x }
+    }
+}
+
+#[unsafe_destructor]
+impl<T: Share + Send> Drop for Weak<T> {
+    fn drop(&mut self) {
+        // see comments above for why this check is here
+        if self.x.is_null() { return }
+
+        // If we find out that we were the last weak pointer, then its time to
+        // deallocate the data entirely. See the discussion in Arc::drop() about
+        // the memory orderings
+        if self.inner().weak.fetch_sub(1, atomics::Release) == 1 {
+            atomics::fence(atomics::Acquire);
+            unsafe { deallocate(self.x as *mut u8, size_of::<ArcInner<T>>(),
+                                min_align_of::<ArcInner<T>>()) }
+        }
+    }
+}
+
+#[cfg(test)]
+#[allow(experimental)]
+mod tests {
+    use std::clone::Clone;
+    use std::comm::channel;
+    use std::mem::drop;
+    use std::ops::{Drop, Deref, DerefMut};
+    use std::option::{Option, Some, None};
+    use std::sync::atomics;
+    use std::task;
+    use std::vec::Vec;
+    use super::{Arc, Weak};
+    use sync::Mutex;
+
+    struct Canary(*mut atomics::AtomicUint);
+
+    impl Drop for Canary
+    {
+        fn drop(&mut self) {
+            unsafe {
+                match *self {
+                    Canary(c) => {
+                        (*c).fetch_add(1, atomics::SeqCst);
+                    }
+                }
+            }
+        }
+    }
+
+    #[test]
+    fn manually_share_arc() {
+        let v = vec!(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
+        let arc_v = Arc::new(v);
+
+        let (tx, rx) = channel();
+
+        task::spawn(proc() {
+            let arc_v: Arc<Vec<int>> = rx.recv();
+            assert_eq!(*arc_v.get(3), 4);
+        });
+
+        tx.send(arc_v.clone());
+
+        assert_eq!(*arc_v.get(2), 3);
+        assert_eq!(*arc_v.get(4), 5);
+
+        info!("{:?}", arc_v);
+    }
+
+    #[test]
+    fn test_cowarc_clone_make_unique() {
+        let mut cow0 = Arc::new(75u);
+        let mut cow1 = cow0.clone();
+        let mut cow2 = cow1.clone();
+
+        assert!(75 == *cow0.make_unique());
+        assert!(75 == *cow1.make_unique());
+        assert!(75 == *cow2.make_unique());
+
+        *cow0.make_unique() += 1;
+        *cow1.make_unique() += 2;
+        *cow2.make_unique() += 3;
+
+        assert!(76 == *cow0);
+        assert!(77 == *cow1);
+        assert!(78 == *cow2);
+
+        // none should point to the same backing memory
+        assert!(*cow0 != *cow1);
+        assert!(*cow0 != *cow2);
+        assert!(*cow1 != *cow2);
+    }
+
+    #[test]
+    fn test_cowarc_clone_unique2() {
+        let mut cow0 = Arc::new(75u);
+        let cow1 = cow0.clone();
+        let cow2 = cow1.clone();
+
+        assert!(75 == *cow0);
+        assert!(75 == *cow1);
+        assert!(75 == *cow2);
+
+        *cow0.make_unique() += 1;
+
+        assert!(76 == *cow0);
+        assert!(75 == *cow1);
+        assert!(75 == *cow2);
+
+        // cow1 and cow2 should share the same contents
+        // cow0 should have a unique reference
+        assert!(*cow0 != *cow1);
+        assert!(*cow0 != *cow2);
+        assert!(*cow1 == *cow2);
+    }
+
+    #[test]
+    fn test_live() {
+        let x = Arc::new(5);
+        let y = x.downgrade();
+        assert!(y.upgrade().is_some());
+    }
+
+    #[test]
+    fn test_dead() {
+        let x = Arc::new(5);
+        let y = x.downgrade();
+        drop(x);
+        assert!(y.upgrade().is_none());
+    }
+
+    #[test]
+    fn weak_self_cyclic() {
+        struct Cycle {
+            x: Mutex<Option<Weak<Cycle>>>
+        }
+
+        let a = Arc::new(Cycle { x: Mutex::new(None) });
+        let b = a.clone().downgrade();
+        *a.deref().x.lock().deref_mut() = Some(b);
+
+        // hopefully we don't double-free (or leak)...
+    }
+
+    #[test]
+    fn drop_arc() {
+        let mut canary = atomics::AtomicUint::new(0);
+        let x = Arc::new(Canary(&mut canary as *mut atomics::AtomicUint));
+        drop(x);
+        assert!(canary.load(atomics::Acquire) == 1);
+    }
+
+    #[test]
+    fn drop_arc_weak() {
+        let mut canary = atomics::AtomicUint::new(0);
+        let arc = Arc::new(Canary(&mut canary as *mut atomics::AtomicUint));
+        let arc_weak = arc.downgrade();
+        assert!(canary.load(atomics::Acquire) == 0);
+        drop(arc);
+        assert!(canary.load(atomics::Acquire) == 1);
+        drop(arc_weak);
+    }
+}
diff --git a/src/liballoc/heap.rs b/src/liballoc/heap.rs
new file mode 100644
index 00000000000..69cd82a981a
--- /dev/null
+++ b/src/liballoc/heap.rs
@@ -0,0 +1,201 @@
+// Copyright 2014 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.
+
+// FIXME: #13994: port to the sized deallocation API when available
+// FIXME: #13996: need a way to mark the `allocate` and `reallocate` return values as `noalias`
+
+use core::intrinsics::{abort, cttz32};
+use core::option::{None, Option};
+use core::ptr::{RawPtr, mut_null, null};
+use libc::{c_char, c_int, c_void, size_t};
+
+#[cfg(not(test))] use core::raw;
+#[cfg(not(test))] use util;
+
+#[link(name = "jemalloc", kind = "static")]
+extern {
+    fn je_mallocx(size: size_t, flags: c_int) -> *mut c_void;
+    fn je_rallocx(ptr: *mut c_void, size: size_t, flags: c_int) -> *mut c_void;
+    fn je_xallocx(ptr: *mut c_void, size: size_t, extra: size_t, flags: c_int) -> size_t;
+    fn je_dallocx(ptr: *mut c_void, flags: c_int);
+    fn je_nallocx(size: size_t, flags: c_int) -> size_t;
+    fn je_malloc_stats_print(write_cb: Option<extern "C" fn(cbopaque: *mut c_void, *c_char)>,
+                             cbopaque: *mut c_void,
+                             opts: *c_char);
+}
+
+// -lpthread needs to occur after -ljemalloc, the earlier argument isn't enough
+#[cfg(not(windows), not(target_os = "android"))]
+#[link(name = "pthread")]
+extern {}
+
+// MALLOCX_ALIGN(a) macro
+#[inline(always)]
+fn mallocx_align(a: uint) -> c_int { unsafe { cttz32(a as u32) as c_int } }
+
+/// Return a pointer to `size` bytes of memory.
+///
+/// Behavior is undefined if the requested size is 0 or the alignment is not a power of 2. The
+/// alignment must be no larger than the largest supported page size on the platform.
+#[inline]
+pub unsafe fn allocate(size: uint, align: uint) -> *mut u8 {
+    let ptr = je_mallocx(size as size_t, mallocx_align(align)) as *mut u8;
+    if ptr.is_null() {
+        abort()
+    }
+    ptr
+}
+
+/// Extend or shrink the allocation referenced by `ptr` to `size` bytes of memory.
+///
+/// Behavior is undefined if the requested size is 0 or the alignment is not a power of 2. The
+/// alignment must be no larger than the largest supported page size on the platform.
+///
+/// The `old_size` and `align` parameters are the parameters that were used to create the
+/// allocation referenced by `ptr`. The `old_size` parameter may also be the value returned by
+/// `usable_size` for the requested size.
+#[inline]
+#[allow(unused_variable)] // for the parameter names in the documentation
+pub unsafe fn reallocate(ptr: *mut u8, size: uint, align: uint, old_size: uint) -> *mut u8 {
+    let ptr = je_rallocx(ptr as *mut c_void, size as size_t, mallocx_align(align)) as *mut u8;
+    if ptr.is_null() {
+        abort()
+    }
+    ptr
+}
+
+/// Extend or shrink the allocation referenced by `ptr` to `size` bytes of memory in-place.
+///
+/// Return true if successful, otherwise false if the allocation was not altered.
+///
+/// Behavior is undefined if the requested size is 0 or the alignment is not a power of 2. The
+/// alignment must be no larger than the largest supported page size on the platform.
+///
+/// The `old_size` and `align` parameters are the parameters that were used to
+/// create the allocation referenced by `ptr`. The `old_size` parameter may be
+/// any value in range_inclusive(requested_size, usable_size).
+#[inline]
+#[allow(unused_variable)] // for the parameter names in the documentation
+pub unsafe fn reallocate_inplace(ptr: *mut u8, size: uint, align: uint, old_size: uint) -> bool {
+    je_xallocx(ptr as *mut c_void, size as size_t, 0, mallocx_align(align)) == size as size_t
+}
+
+/// Deallocate the memory referenced by `ptr`.
+///
+/// The `ptr` parameter must not be null.
+///
+/// The `size` and `align` parameters are the parameters that were used to create the
+/// allocation referenced by `ptr`. The `size` parameter may also be the value returned by
+/// `usable_size` for the requested size.
+#[inline]
+#[allow(unused_variable)] // for the parameter names in the documentation
+pub unsafe fn deallocate(ptr: *mut u8, size: uint, align: uint) {
+    je_dallocx(ptr as *mut c_void, mallocx_align(align))
+}
+
+/// Return the usable size of an allocation created with the specified the `size` and `align`.
+#[inline]
+pub fn usable_size(size: uint, align: uint) -> uint {
+    unsafe { je_nallocx(size as size_t, mallocx_align(align)) as uint }
+}
+
+/// Print implementation-defined allocator statistics.
+///
+/// These statistics may be inconsistent if other threads use the allocator during the call.
+#[unstable]
+pub fn stats_print() {
+    unsafe {
+        je_malloc_stats_print(None, mut_null(), null())
+    }
+}
+
+/// The allocator for unique pointers.
+#[cfg(not(test))]
+#[lang="exchange_malloc"]
+#[inline(always)]
+pub unsafe fn exchange_malloc_(size: uint, align: uint) -> *mut u8 {
+    exchange_malloc(size, align)
+}
+
+/// The allocator for unique pointers.
+#[inline]
+pub unsafe fn exchange_malloc(size: uint, align: uint) -> *mut u8 {
+    // The compiler never calls `exchange_free` on ~ZeroSizeType, so zero-size
+    // allocations can point to this `static`. It would be incorrect to use a null
+    // pointer, due to enums assuming types like unique pointers are never null.
+    static EMPTY: () = ();
+
+    if size == 0 {
+        &EMPTY as *() as *mut u8
+    } else {
+        allocate(size, align)
+    }
+}
+
+#[cfg(not(test))]
+#[lang="exchange_free"]
+#[inline]
+// FIXME: #13994 (rustc should pass align and size here)
+unsafe fn exchange_free(ptr: *mut u8) {
+    deallocate(ptr, 0, 8);
+}
+
+// FIXME: #7496
+#[cfg(not(test))]
+#[lang="closure_exchange_malloc"]
+#[inline]
+#[allow(deprecated)]
+unsafe fn closure_exchange_malloc(drop_glue: fn(*mut u8), size: uint, align: uint) -> *mut u8 {
+    let total_size = util::get_box_size(size, align);
+    let p = allocate(total_size, 8);
+
+    let alloc = p as *mut raw::Box<()>;
+    (*alloc).drop_glue = drop_glue;
+
+    alloc as *mut u8
+}
+
+// hack for libcore
+#[no_mangle]
+#[doc(hidden)]
+#[deprecated]
+#[cfg(not(test))]
+pub unsafe extern "C" fn rust_malloc(size: uint, align: uint) -> *mut u8 {
+    exchange_malloc(size, align)
+}
+
+// hack for libcore
+#[no_mangle]
+#[doc(hidden)]
+#[deprecated]
+#[cfg(not(test))]
+pub unsafe extern "C" fn rust_free(ptr: *mut u8, size: uint, align: uint) {
+    deallocate(ptr, size, align)
+}
+
+#[cfg(test)]
+mod bench {
+    extern crate test;
+    use self::test::Bencher;
+
+    #[bench]
+    fn alloc_owned_small(b: &mut Bencher) {
+        b.iter(|| {
+            box 10
+        })
+    }
+
+    #[bench]
+    fn alloc_owned_big(b: &mut Bencher) {
+        b.iter(|| {
+            box [10, ..1000]
+        })
+    }
+}
diff --git a/src/liballoc/lib.rs b/src/liballoc/lib.rs
new file mode 100644
index 00000000000..1a6d7bfaed0
--- /dev/null
+++ b/src/liballoc/lib.rs
@@ -0,0 +1,101 @@
+// Copyright 2014 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.
+
+//! Rust's core allocation library
+//!
+//! This is the lowest level library through which allocation in Rust can be
+//! performed where the allocation is assumed to succeed. This library will
+//! trigger a task failure when allocation fails.
+//!
+//! This library, like libcore, is not intended for general usage, but rather as
+//! a building block of other libraries. The types and interfaces in this
+//! library are reexported through the [standard library](../std/index.html),
+//! and should not be used through this library.
+//!
+//! Currently, there are four major definitions in this library.
+//!
+//! ## Owned pointers
+//!
+//! The [`Box`](owned/index.html) type is the core owned pointer type in rust.
+//! There can only be one owner of a `Box`, and the owner can decide to mutate
+//! the contents.
+//!
+//! This type can be sent among tasks efficiently as the size of a `Box` value
+//! is just a pointer. Tree-like data structures are often built on owned
+//! pointers because each node often has only one owner, the parent.
+//!
+//! ## Reference counted pointers
+//!
+//! The [`Rc`](rc/index.html) type is a non-threadsafe reference-counted pointer
+//! type intended for sharing memory within a task. An `Rc` pointer wraps a
+//! type, `T`, and only allows access to `&T`, a shared reference.
+//!
+//! This type is useful when inherited mutability is too constraining for an
+//! application (such as using `Box`), and is often paired with the `Cell` or
+//! `RefCell` types in order to allow mutation.
+//!
+//! ## Atomically reference counted pointers
+//!
+//! The [`Arc`](arc/index.html) type is the threadsafe equivalent of the `Rc`
+//! type. It provides all the same functionality of `Rc`, except it requires
+//! that the contained type `T` is shareable. Additionally, `Arc<T>` is itself
+//! sendable while `Rc<T>` is not.
+//!
+//! This types allows for shared access to the contained data, and is often
+//! paired with synchronization primitives such as mutexes to allow mutation of
+//! shared resources.
+//!
+//! ## Heap interfaces
+//!
+//! The [`heap`](heap/index.html) and [`libc_heap`](libc_heap/index.html)
+//! modules are the unsafe interfaces to the underlying allocation systems. The
+//! `heap` module is considered the default heap, and is not necessarily backed
+//! by libc malloc/free.  The `libc_heap` module is defined to be wired up to
+//! the system malloc/free.
+
+#![crate_id = "alloc#0.11.0-pre"]
+#![license = "MIT/ASL2"]
+#![crate_type = "rlib"]
+#![doc(html_logo_url = "http://www.rust-lang.org/logos/rust-logo-128x128-blk-v2.png",
+       html_favicon_url = "http://www.rust-lang.org/favicon.ico",
+       html_root_url = "http://static.rust-lang.org/doc/master")]
+
+#![no_std]
+#![feature(phase)]
+
+#[phase(syntax, link)]
+extern crate core;
+extern crate libc;
+
+// Allow testing this library
+
+#[cfg(test)] extern crate sync;
+#[cfg(test)] extern crate native;
+#[cfg(test)] #[phase(syntax, link)] extern crate std;
+#[cfg(test)] #[phase(syntax, link)] extern crate log;
+
+// Heaps provided for low-level allocation strategies
+
+pub mod heap;
+pub mod libc_heap;
+pub mod util;
+
+// Primitive types using the heaps above
+
+#[cfg(not(test))]
+pub mod owned;
+pub mod arc;
+pub mod rc;
+
+#[cfg(not(test))]
+mod std {
+    pub use core::fmt;
+    pub use core::option;
+}
diff --git a/src/liballoc/libc_heap.rs b/src/liballoc/libc_heap.rs
new file mode 100644
index 00000000000..5b189bc672e
--- /dev/null
+++ b/src/liballoc/libc_heap.rs
@@ -0,0 +1,51 @@
+// Copyright 2012 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.
+
+
+//! The global (exchange) heap.
+
+use libc::{c_void, size_t, free, malloc, realloc};
+use core::ptr::{RawPtr, mut_null};
+use core::intrinsics::abort;
+
+/// A wrapper around libc::malloc, aborting on out-of-memory
+#[inline]
+pub unsafe fn malloc_raw(size: uint) -> *mut u8 {
+    // `malloc(0)` may allocate, but it may also return a null pointer
+    // http://pubs.opengroup.org/onlinepubs/9699919799/functions/malloc.html
+    if size == 0 {
+        mut_null()
+    } else {
+        let p = malloc(size as size_t);
+        if p.is_null() {
+            // we need a non-allocating way to print an error here
+            abort();
+        }
+        p as *mut u8
+    }
+}
+
+/// A wrapper around libc::realloc, aborting on out-of-memory
+#[inline]
+pub unsafe fn realloc_raw(ptr: *mut u8, size: uint) -> *mut u8 {
+    // `realloc(ptr, 0)` may allocate, but it may also return a null pointer
+    // http://pubs.opengroup.org/onlinepubs/9699919799/functions/realloc.html
+    if size == 0 {
+        free(ptr as *mut c_void);
+        mut_null()
+    } else {
+        let p = realloc(ptr as *mut c_void, size as size_t);
+        if p.is_null() {
+            // we need a non-allocating way to print an error here
+            abort();
+        }
+        p as *mut u8
+    }
+}
diff --git a/src/liballoc/owned.rs b/src/liballoc/owned.rs
new file mode 100644
index 00000000000..30e0fe6c4dd
--- /dev/null
+++ b/src/liballoc/owned.rs
@@ -0,0 +1,115 @@
+// Copyright 2012 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.
+
+//! A unique pointer type
+
+use core::any::{Any, AnyRefExt};
+use core::clone::Clone;
+use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering};
+use core::default::Default;
+use core::fmt;
+use core::intrinsics;
+use core::mem;
+use core::raw::TraitObject;
+use core::result::{Ok, Err, Result};
+
+/// A value that represents the global exchange heap. This is the default
+/// place that the `box` keyword allocates into when no place is supplied.
+///
+/// The following two examples are equivalent:
+///
+///     let foo = box(HEAP) Bar::new(...);
+///     let foo = box Bar::new(...);
+#[lang="exchange_heap"]
+pub static HEAP: () = ();
+
+/// A type that represents a uniquely-owned value.
+#[lang="owned_box"]
+pub struct Box<T>(*T);
+
+impl<T: Default> Default for Box<T> {
+    fn default() -> Box<T> { box Default::default() }
+}
+
+impl<T: Clone> Clone for Box<T> {
+    /// Return a copy of the owned box.
+    #[inline]
+    fn clone(&self) -> Box<T> { box {(**self).clone()} }
+
+    /// Perform copy-assignment from `source` by reusing the existing allocation.
+    #[inline]
+    fn clone_from(&mut self, source: &Box<T>) {
+        (**self).clone_from(&(**source));
+    }
+}
+
+// box pointers
+impl<T:Eq> Eq for Box<T> {
+    #[inline]
+    fn eq(&self, other: &Box<T>) -> bool { *(*self) == *(*other) }
+    #[inline]
+    fn ne(&self, other: &Box<T>) -> bool { *(*self) != *(*other) }
+}
+impl<T:Ord> Ord for Box<T> {
+    #[inline]
+    fn lt(&self, other: &Box<T>) -> bool { *(*self) < *(*other) }
+    #[inline]
+    fn le(&self, other: &Box<T>) -> bool { *(*self) <= *(*other) }
+    #[inline]
+    fn ge(&self, other: &Box<T>) -> bool { *(*self) >= *(*other) }
+    #[inline]
+    fn gt(&self, other: &Box<T>) -> bool { *(*self) > *(*other) }
+}
+impl<T: TotalOrd> TotalOrd for Box<T> {
+    #[inline]
+    fn cmp(&self, other: &Box<T>) -> Ordering { (**self).cmp(*other) }
+}
+impl<T: TotalEq> TotalEq for Box<T> {}
+
+/// Extension methods for an owning `Any` trait object
+pub trait AnyOwnExt {
+    /// Returns the boxed value if it is of type `T`, or
+    /// `Err(Self)` if it isn't.
+    fn move<T: 'static>(self) -> Result<Box<T>, Self>;
+}
+
+impl AnyOwnExt for Box<Any> {
+    #[inline]
+    fn move<T: 'static>(self) -> Result<Box<T>, Box<Any>> {
+        if self.is::<T>() {
+            unsafe {
+                // Get the raw representation of the trait object
+                let to: TraitObject =
+                    *mem::transmute::<&Box<Any>, &TraitObject>(&self);
+
+                // Prevent destructor on self being run
+                intrinsics::forget(self);
+
+                // Extract the data pointer
+                Ok(mem::transmute(to.data))
+            }
+        } else {
+            Err(self)
+        }
+    }
+}
+
+impl<T: fmt::Show> fmt::Show for Box<T> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        (**self).fmt(f)
+    }
+}
+
+#[cfg(not(stage0))]
+impl fmt::Show for Box<Any> {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.pad("Box<Any>")
+    }
+}
diff --git a/src/liballoc/rc.rs b/src/liballoc/rc.rs
new file mode 100644
index 00000000000..5a877d9362e
--- /dev/null
+++ b/src/liballoc/rc.rs
@@ -0,0 +1,303 @@
+// Copyright 2013 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.
+
+/*! Task-local reference-counted boxes (`Rc` type)
+
+The `Rc` type provides shared ownership of an immutable value. Destruction is deterministic, and
+will occur as soon as the last owner is gone. It is marked as non-sendable because it avoids the
+overhead of atomic reference counting.
+
+The `downgrade` method can be used to create a non-owning `Weak` pointer to the box. A `Weak`
+pointer can be upgraded to an `Rc` pointer, but will return `None` if the value has already been
+freed.
+
+For example, a tree with parent pointers can be represented by putting the nodes behind `Strong`
+pointers, and then storing the parent pointers as `Weak` pointers.
+
+*/
+
+use core::mem::transmute;
+use core::cell::Cell;
+use core::clone::Clone;
+use core::cmp::{Eq, Ord, TotalEq, TotalOrd, Ordering};
+use core::kinds::marker;
+use core::ops::{Deref, Drop};
+use core::option::{Option, Some, None};
+use core::ptr;
+use core::ptr::RawPtr;
+use core::mem::{min_align_of, size_of};
+
+use heap::deallocate;
+
+struct RcBox<T> {
+    value: T,
+    strong: Cell<uint>,
+    weak: Cell<uint>
+}
+
+/// Immutable reference counted pointer type
+#[unsafe_no_drop_flag]
+pub struct Rc<T> {
+    ptr: *mut RcBox<T>,
+    nosend: marker::NoSend,
+    noshare: marker::NoShare
+}
+
+impl<T> Rc<T> {
+    /// Construct a new reference-counted box
+    pub fn new(value: T) -> Rc<T> {
+        unsafe {
+            Rc {
+                // there is an implicit weak pointer owned by all the
+                // strong pointers, which ensures that the weak
+                // destructor never frees the allocation while the
+                // strong destructor is running, even if the weak
+                // pointer is stored inside the strong one.
+                ptr: transmute(box RcBox {
+                    value: value,
+                    strong: Cell::new(1),
+                    weak: Cell::new(1)
+                }),
+                nosend: marker::NoSend,
+                noshare: marker::NoShare
+            }
+        }
+    }
+}
+
+impl<T> Rc<T> {
+    /// Downgrade the reference-counted pointer to a weak reference
+    pub fn downgrade(&self) -> Weak<T> {
+        self.inc_weak();
+        Weak {
+            ptr: self.ptr,
+            nosend: marker::NoSend,
+            noshare: marker::NoShare
+        }
+    }
+}
+
+impl<T> Deref<T> for Rc<T> {
+    /// Borrow the value contained in the reference-counted box
+    #[inline(always)]
+    fn deref<'a>(&'a self) -> &'a T {
+        &self.inner().value
+    }
+}
+
+#[unsafe_destructor]
+impl<T> Drop for Rc<T> {
+    fn drop(&mut self) {
+        unsafe {
+            if !self.ptr.is_null() {
+                self.dec_strong();
+                if self.strong() == 0 {
+                    ptr::read(self.deref()); // destroy the contained object
+
+                    // remove the implicit "strong weak" pointer now
+                    // that we've destroyed the contents.
+                    self.dec_weak();
+
+                    if self.weak() == 0 {
+                        deallocate(self.ptr as *mut u8, size_of::<RcBox<T>>(),
+                                   min_align_of::<RcBox<T>>())
+                    }
+                }
+            }
+        }
+    }
+}
+
+impl<T> Clone for Rc<T> {
+    #[inline]
+    fn clone(&self) -> Rc<T> {
+        self.inc_strong();
+        Rc { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare }
+    }
+}
+
+impl<T: Eq> Eq for Rc<T> {
+    #[inline(always)]
+    fn eq(&self, other: &Rc<T>) -> bool { **self == **other }
+    #[inline(always)]
+    fn ne(&self, other: &Rc<T>) -> bool { **self != **other }
+}
+
+impl<T: TotalEq> TotalEq for Rc<T> {}
+
+impl<T: Ord> Ord for Rc<T> {
+    #[inline(always)]
+    fn lt(&self, other: &Rc<T>) -> bool { **self < **other }
+
+    #[inline(always)]
+    fn le(&self, other: &Rc<T>) -> bool { **self <= **other }
+
+    #[inline(always)]
+    fn gt(&self, other: &Rc<T>) -> bool { **self > **other }
+
+    #[inline(always)]
+    fn ge(&self, other: &Rc<T>) -> bool { **self >= **other }
+}
+
+impl<T: TotalOrd> TotalOrd for Rc<T> {
+    #[inline]
+    fn cmp(&self, other: &Rc<T>) -> Ordering { (**self).cmp(&**other) }
+}
+
+/// Weak reference to a reference-counted box
+#[unsafe_no_drop_flag]
+pub struct Weak<T> {
+    ptr: *mut RcBox<T>,
+    nosend: marker::NoSend,
+    noshare: marker::NoShare
+}
+
+impl<T> Weak<T> {
+    /// Upgrade a weak reference to a strong reference
+    pub fn upgrade(&self) -> Option<Rc<T>> {
+        if self.strong() == 0 {
+            None
+        } else {
+            self.inc_strong();
+            Some(Rc { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare })
+        }
+    }
+}
+
+#[unsafe_destructor]
+impl<T> Drop for Weak<T> {
+    fn drop(&mut self) {
+        unsafe {
+            if !self.ptr.is_null() {
+                self.dec_weak();
+                // the weak count starts at 1, and will only go to
+                // zero if all the strong pointers have disappeared.
+                if self.weak() == 0 {
+                    deallocate(self.ptr as *mut u8, size_of::<RcBox<T>>(),
+                               min_align_of::<RcBox<T>>())
+                }
+            }
+        }
+    }
+}
+
+impl<T> Clone for Weak<T> {
+    #[inline]
+    fn clone(&self) -> Weak<T> {
+        self.inc_weak();
+        Weak { ptr: self.ptr, nosend: marker::NoSend, noshare: marker::NoShare }
+    }
+}
+
+#[doc(hidden)]
+trait RcBoxPtr<T> {
+    fn inner<'a>(&'a self) -> &'a RcBox<T>;
+
+    #[inline]
+    fn strong(&self) -> uint { self.inner().strong.get() }
+
+    #[inline]
+    fn inc_strong(&self) { self.inner().strong.set(self.strong() + 1); }
+
+    #[inline]
+    fn dec_strong(&self) { self.inner().strong.set(self.strong() - 1); }
+
+    #[inline]
+    fn weak(&self) -> uint { self.inner().weak.get() }
+
+    #[inline]
+    fn inc_weak(&self) { self.inner().weak.set(self.weak() + 1); }
+
+    #[inline]
+    fn dec_weak(&self) { self.inner().weak.set(self.weak() - 1); }
+}
+
+impl<T> RcBoxPtr<T> for Rc<T> {
+    #[inline(always)]
+    fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
+}
+
+impl<T> RcBoxPtr<T> for Weak<T> {
+    #[inline(always)]
+    fn inner<'a>(&'a self) -> &'a RcBox<T> { unsafe { &(*self.ptr) } }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::{Rc, Weak};
+    use std::cell::RefCell;
+    use std::option::{Option, Some, None};
+    use std::mem::drop;
+    use std::clone::Clone;
+
+    #[test]
+    fn test_clone() {
+        let x = Rc::new(RefCell::new(5));
+        let y = x.clone();
+        *x.borrow_mut() = 20;
+        assert_eq!(*y.borrow(), 20);
+    }
+
+    #[test]
+    fn test_simple() {
+        let x = Rc::new(5);
+        assert_eq!(*x, 5);
+    }
+
+    #[test]
+    fn test_simple_clone() {
+        let x = Rc::new(5);
+        let y = x.clone();
+        assert_eq!(*x, 5);
+        assert_eq!(*y, 5);
+    }
+
+    #[test]
+    fn test_destructor() {
+        let x = Rc::new(box 5);
+        assert_eq!(**x, 5);
+    }
+
+    #[test]
+    fn test_live() {
+        let x = Rc::new(5);
+        let y = x.downgrade();
+        assert!(y.upgrade().is_some());
+    }
+
+    #[test]
+    fn test_dead() {
+        let x = Rc::new(5);
+        let y = x.downgrade();
+        drop(x);
+        assert!(y.upgrade().is_none());
+    }
+
+    #[test]
+    fn gc_inside() {
+        // see issue #11532
+        use std::gc::Gc;
+        let a = Rc::new(RefCell::new(Gc::new(1)));
+        assert!(a.try_borrow_mut().is_some());
+    }
+
+    #[test]
+    fn weak_self_cyclic() {
+        struct Cycle {
+            x: RefCell<Option<Weak<Cycle>>>
+        }
+
+        let a = Rc::new(Cycle { x: RefCell::new(None) });
+        let b = a.clone().downgrade();
+        *a.x.borrow_mut() = Some(b);
+
+        // hopefully we don't double-free (or leak)...
+    }
+}
diff --git a/src/liballoc/util.rs b/src/liballoc/util.rs
new file mode 100644
index 00000000000..7e35af79eab
--- /dev/null
+++ b/src/liballoc/util.rs
@@ -0,0 +1,30 @@
+// Copyright 2013 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.
+
+#![doc(hidden)]
+
+use core::mem;
+use core::raw;
+
+#[inline]
+#[deprecated]
+pub fn get_box_size(body_size: uint, body_align: uint) -> uint {
+    let header_size = mem::size_of::<raw::Box<()>>();
+    let total_size = align_to(header_size, body_align) + body_size;
+    total_size
+}
+
+// Rounds size to the next alignment. Alignment is required to be a power of
+// two.
+#[inline]
+fn align_to(size: uint, align: uint) -> uint {
+    assert!(align != 0);
+    (size + align - 1) & !(align - 1)
+}