rust-lang/rust

alloc

library/alloc/ is the layer between core and std. It assumes the existence of a global allocator and provides heap-allocated container types.

Purpose

alloc adds:

Box<T> — single-owner heap allocation
Vec<T> — growable array
String — growable UTF-8 string (built on Vec<u8>)
Rc<T>, Arc<T> — reference-counted pointers
BTreeMap, BTreeSet — ordered map/set (B-tree implementation)
VecDeque — growable double-ended queue
LinkedList — doubly linked list
BinaryHeap — priority queue
Cow<T> — clone-on-write smart pointer
The Vec macro vec![1, 2, 3]
format! and the formatting glue that needs String

It does not include HashMap or HashSet — those need a randomness source (DOS resistance) and live in std.

Why a separate crate

alloc exists to support #![no_std] programs that do have an allocator (most embedded operating systems, kernels with kernel-mode allocators, WebAssembly with a custom allocator). They opt in:

#![no_std]
extern crate alloc;
use alloc::vec::Vec;

In a regular std program, you don't see alloc directly because std re-exports its types: std::vec::Vec is alloc::vec::Vec, std::string::String is alloc::string::String. Cargo.toml and the prelude take care of glueing it together.

Directory layout

library/alloc/
├── Cargo.toml
├── src/
│   ├── lib.rs              # Crate root, re-exports
│   ├── alloc.rs            # GlobalAlloc trait + glue
│   ├── boxed.rs            # Box<T>
│   ├── vec/                # Vec<T> + IntoIter, Drain, Splice, …
│   ├── string.rs           # String + Drain, FromUtf8Error
│   ├── slice.rs            # Owned slice operations (joined/concat/sort_by_key)
│   ├── rc.rs               # Rc<T>, Weak<T>
│   ├── sync.rs             # Arc<T>, Weak<T>
│   ├── collections/
│   │   ├── btree/          # BTreeMap, BTreeSet
│   │   ├── linked_list.rs
│   │   ├── vec_deque/
│   │   └── binary_heap.rs
│   ├── borrow.rs           # Cow<T>
│   ├── fmt.rs              # format!, Format, Display, …
│   ├── raw_vec.rs          # internal RawVec backing store
│   └── ...

Key abstractions

Type	Where	Notes
`Box<T>`	`alloc::boxed`	Single owner; `#[lang = "owned_box"]`
`Vec<T>`	`alloc::vec`	Backed by `RawVec<T>`
`RawVec<T>`	`alloc::raw_vec`	Internal: pointer + capacity + allocator
`String`	`alloc::string`	`Vec<u8>` + UTF-8 invariants
`Rc<T>`	`alloc::rc`	Single-threaded refcount
`Arc<T>`	`alloc::sync`	Atomic refcount; thread-safe
`Weak<T>`	`alloc::rc`, `alloc::sync`	Non-owning weak ref
`BTreeMap<K, V>`	`alloc::collections::btree`	B-tree (better cache behavior than red-black tree)
`Cow<'a, B>`	`alloc::borrow`	Borrowed-or-owned smart pointer

The allocator API

alloc::alloc defines:

Layout (re-export from core::alloc::Layout) — size + alignment
GlobalAlloc — trait for global allocators
alloc(), dealloc(), realloc() — the unsafe primitives

#[global_allocator] static A: MyAlloc = MyAlloc; registers a custom allocator. The default in std is the system allocator (std::alloc::System); rustc itself uses jemalloc on CI builds (see compiler/rustc/src/main.rs).

There's also an unstable Allocator trait (#![feature(allocator_api)]) that lets containers be parameterized over an allocator: Vec<T, A: Allocator>. This is still being designed; see the tracking issue.

How `Vec` works

Vec<T> is a workhorse and a good example of alloc design:

pub struct Vec<T, A: Allocator = Global> {
    buf: RawVec<T, A>,
    len: usize,
}

struct RawVec<T, A: Allocator> {
    ptr: NonNull<T>,
    cap: Cap,         // packed capacity + niche
    alloc: A,
}

The growth strategy is doubling (sometimes 2x, sometimes via RawVec::reserve)
Drop semantics are subtle: drop the elements, then deallocate the buffer
IntoIter takes ownership and walks elements without deallocating until done
ZST optimization: zero-sized types use a dangling pointer and skip allocation

The vec module spans 10+ files; the splits are by feature (Drain, Splice, IntoIter, ExtractIf, …).

How `Rc` and `Arc` differ

Both are reference-counted, but:

Rc<T> uses a non-atomic counter — fast, single-threaded only
Arc<T> uses atomic counters — usable across threads, slightly slower
The Weak<T> strong-count vs. weak-count protocol is the same in both
Rc::downgrade(&rc) returns a Weak<T> whose upgrade() may return None

The interior layout is RcInner<T> { strong: Cell<usize>, weak: Cell<usize>, value: T } (Cell for Rc; AtomicUsize for Arc). The pointer points to the value, not the header — accessing the counts goes via (ptr as *const u8).offset(-...).

Lang items in `alloc`

Several allocation-related lang items live here:

#[lang = "owned_box"] on Box<T>
#[lang = "exchange_malloc"] on the alloc::alloc::exchange_malloc shim used by box syntax (now mostly desugared in MIR build)

Runtime allocator hooks like __rust_alloc, __rust_dealloc, __rust_realloc are emitted by the compiler when the allocator-shim mode is in use.

Testing

Like core, alloc has its own external test crate at library/alloctests/.

./x test library/alloc

Tests are invariant-heavy: Vec invariants, Rc count integrity, String UTF-8, B-tree balance, etc.

Entry points for modification

New method on Vec/String/BTreeMap → corresponding alloc::* source file; ACP first
Allocator API changes → very high-touch, coordinate with libs-api
Performance work — the implementations here are micro-optimized; benchmark before and after