Skip to content
Tutorials Center
My learning

Topics

Lesson 109 of 132 ยท Advanced Rust

Building Data Structures with Unsafe

Build a Vec clone on std::alloc and a raw-pointer queue in Rust, learn the invariants, Drop, PhantomData, SAFETY comments, leak counting and how Miri finds undefined behavior.

Almost every data structure in the standard library, Vec, VecDeque, HashMap, Rc, Mutex, is built on unsafe code. That is not a failure of Rust; it is the design. The borrow checker cannot understand "this buffer has room for eight elements but only three are initialized" or "this node is reachable from two pointers". Someone has to state those facts to the compiler, and unsafe is the way to say "I checked this part myself". The art is to keep the unsafe code small, wrap it in a safe API and write down the invariants that make it correct.

In this lesson you will build two real structures from scratch: a growable array, MyVec<T>, directly on the allocator, and a FIFO queue made of heap nodes joined by raw pointers. You will learn how to reason about each unsafe block, how Drop and PhantomData fit in, and how to detect leaks and double drops with a simple counter. Read Unsafe Rust first for the five unsafe powers, raw pointers and undefined behavior, and Drop and RAII for destructors.

Everything here is for learning. In real programs use Vec, VecDeque and LinkedList from std. Write your own unsafe containers only when you can show that the standard ones do not fit, and test them with Miri (see the end of this lesson).

The recipe: invariants first

Before writing any unsafe code, write down the invariants: facts that are always true between calls of the safe API. For a vector they are:

  1. ptr is either dangling (when cap == 0) or points to an allocation that fits exactly cap values of T, with the right alignment.
  2. The first len slots hold initialized values; the remaining cap - len are uninitialized memory.
  3. len <= cap.
  4. The vector owns its elements: when it is dropped, it must drop each of the len values once, and free the allocation once.

Each unsafe block then needs one comment that says why the block keeps these true. The convention is // SAFETY:. If you cannot write that sentence, the block is not ready.

Pointers need an unsafe block

Raw pointers can be created and compared safely, but reading or writing through them is unsafe, because the compiler cannot know the address is valid. Here is the error you get if you forget:

Rust Reading through a raw pointer needs unsafe (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The compiler refuses with error[E0133]: call to unsafe function std::ptr::read is unsafe and requires unsafe block, and the note "consult the function's documentation for information on how to avoid undefined behavior". The fix is unsafe { std::ptr::read(p) }, with a SAFETY comment explaining why p is valid here (it came from a live reference).

Step 1: a growable array on std::alloc

std::alloc is the low-level interface to the global allocator. A Layout describes size and alignment; alloc returns a raw *mut u8 (or null on failure); realloc resizes and dealloc frees. Layout::array::<T>(n) computes the layout of n values of T and returns an error on overflow.

Our struct stores a NonNull<T>, a pointer that is guaranteed non-null (which also lets Option<MyVec<T>> use the null value as None), plus the capacity and length. PhantomData<T> tells the compiler and the drop checker that the vector owns values of type T.

Rust MyVec: push, pop, remove, slices and Drop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Read the push function slowly, because it is the template for the whole container. grow guarantees len < cap, so add(len) stays inside the allocation. The slot holds garbage, so we must not assign to it (assignment would drop the old value, running a destructor on garbage); write stores the bytes without reading or dropping anything. pop does the opposite: read copies the value out and the vector forgets the slot by decreasing len first.

remove is the first place where overlap matters. We shift the tail one slot left, and the source and destination ranges overlap, so we need ptr::copy (like C's memmove), not ptr::copy_nonoverlapping (memcpy), which would be undefined behavior here. Choosing the wrong one compiles and often even works, which is exactly why unsafe code needs reasoning rather than testing alone.

Finally, Deref<Target = [T]> is a very cheap way to inherit a hundred slice methods (iter, sort, first, binary_search, indexing) without writing them.

Two things this toy skips. Zero-sized types: for them Layout::array has size 0 and alloc must not be called, so the real Vec special-cases them and treats the capacity as infinite. Panic safety: if T's destructor panics inside drop_in_place, the allocation leaks; the real implementation uses a guard type so the memory is still freed.

Step 2: counting to catch leaks and double drops

How do you test that Drop is right? You make the elements observable. A tiny type whose constructor increments a global counter and whose destructor decrements it tells you how many values are alive at any moment. After the container is gone the counter must be zero. A leak leaves it above zero. A double drop pushes the count below zero, or panics in the subtraction when you use a checked counter.

Rust A counter reveals leaks and drops

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

The first block shows the healthy case; the second plays the part of a bug where Drop never runs, and the counter exposes it. Use the same trick for other invariants: count clones, count drop calls per element and assert each element was dropped exactly once, or record the order of drops in a Vec<u32> behind a mutex and compare it with the expected order.

Counters catch the mistakes that change behavior. Some undefined behavior has no visible symptom at all (reading uninitialized memory, a misaligned pointer, an aliasing violation), and the optimizer may turn it into a bug only in release mode on another day. For those you need a tool that checks the rules, which is Miri, covered below.

Step 3: a queue made of raw-pointer nodes

A queue needs fast push_back and pop_front, so we keep a pointer to both ends of a singly linked list. In safe Rust this is painful, because the last node is reachable through the chain and through tail: two paths to one object, one of them mutable. Raw pointers do not have an aliasing rule at the moment you create them, so we can express it, and our safe API will make sure only valid operations are possible.

Ownership plan: every node is allocated by Box::new and handed over to the queue as a raw pointer with Box::into_raw; the queue owns it until it gives it back with Box::from_raw, which re-creates the Box so the normal drop logic frees the memory. Using Box for allocation means we never touch std::alloc and cannot mismatch layouts.

Rust A FIFO queue with head and tail pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.

Notice what the safe API hides. Nobody can reach a *mut Node; users see only &T, Option<T> and an iterator. The invariants are: head and tail are both null or both non-null; every non-null node pointer came from Box::into_raw and is freed exactly once by pop_front; tail points to the node whose next is null. Resetting tail to null when the last node is popped is the classic bug: forget it and the next push_back writes through a freed node, which is undefined behavior that may appear to work.

The Iter struct shows PhantomData<&'a T> at work. It stores only raw pointers, so without the marker the compiler would see no connection between the iterator and the queue and would allow queue.pop_front() while the iterator is alive. With it, the iterator borrows the queue and the borrow checker enforces the rule for us.

Last, Drop pops until empty. If we simply let the nodes drop recursively (as a naive Box<Node> list does), a 200,000 element list would recurse once per node and overflow the stack.

Send, Sync and variance come for free (and sometimes wrongly)

A struct containing raw pointers is automatically !Send and !Sync, which is the safe default: the compiler cannot know that sharing is sound. If your container really behaves like Vec<T> (owns its data, no hidden shared state), you can promise it manually:

Rust
// SAFETY: MyVec owns its elements like Vec<T>, so it is Send/Sync exactly when T is.
unsafe impl<T: Send> Send for MyVec<T> {}
unsafe impl<T: Sync> Sync for MyVec<T> {}

These unsafe impls are claims you make for all future code, so double-check that no Rc-like sharing exists. Also remember variance: NonNull<T> is covariant like &T, while *mut T is invariant. Our queue uses *mut, so Queue<&'long str> cannot be shrunk to Queue<&'short str> implicitly. That is safe and merely less flexible; Vec uses NonNull plus PhantomData<T> to be covariant, which is correct for it. See Type System Techniques for what variance means and Send and Sync for the traits.

Testing unsafe code with Miri

Ordinary tests only show that one execution did not crash. Miri is an interpreter for Rust's mid-level IR that checks each operation against the language rules. It reports out-of-bounds access, use after free, uninitialized reads, misaligned pointers, invalid values (a bool that is not 0 or 1), double frees, leaks and violations of the aliasing model (Stacked Borrows or Tree Borrows). It is slow, so you run it on your unit tests, not on production workloads.

This is a read-only session, because Miri needs a nightly toolchain and Cargo, which our online editor does not offer:

Terminal
rustup +nightly component add miri
cargo +nightly miri test
# optional: a different seed explores other thread interleavings
MIRIFLAGS="-Zmiri-seed=7" cargo +nightly miri test

A good workflow: write the safe API, add // SAFETY: comments, write tests that include the awkward cases (empty container, one element, grow across a capacity boundary, remove at both ends, panic in a destructor), and run them under Miri in CI. Combine it with the counting trick from above. Two supporting lints help too: #![deny(unsafe_op_in_unsafe_fn)] (already a warning in the 2024 edition) requires an explicit unsafe block even inside unsafe fn, and clippy::undocumented_unsafe_blocks insists on SAFETY comments.

Common mistakes

  • Assigning into uninitialized memory (*ptr = value) instead of ptr.write(value): the assignment drops garbage.
  • Using copy_nonoverlapping on overlapping ranges: use ptr::copy.
  • Forgetting to update len before reading out or after writing, so a panic or early return leaves a double owner.
  • Creating a &mut while another pointer is still in use and then using the other pointer: the aliasing model says the first one's access is now invalid.
  • Freeing with a different Layout than the allocation used.
  • Dangling tail/prev pointers after removing the last node.
  • Missing PhantomData, so the drop checker or the borrow checker is not told about ownership or borrowing.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does push use ptr.add(len).write(value) instead of *ptr.add(len) = value?

    Assigning through a pointer drops the previous value. The slot holds garbage, so running a destructor on it would be undefined behavior; write just stores the bytes.
  2. 2. Why must remove use ptr::copy rather than ptr::copy_nonoverlapping?

    copy_nonoverlapping is like memcpy and requires disjoint ranges. Shifting the tail by one slot overlaps, so you need ptr::copy (like memmove).
  3. 3. What does the LIVE counter in the leak test measure?

    The constructor increments and Drop decrements the counter, so it is the number of live values. After the container is gone it must be zero.
  4. 4. In Queue::pop_front, what bug appears if you forget to set tail to null when the queue becomes empty?

    tail would point to the node that was just freed. push_back then does (*self.tail).next = node on freed memory.
  5. 5. Why does Iter<'a, T> contain PhantomData<&'a T>?

    Raw pointers carry no lifetime. The marker restores the borrow relationship so the queue cannot be mutated while the iterator lives.

Summary

  • Write down the invariants of the structure first; every unsafe block gets a // SAFETY: comment explaining why it preserves them.
  • MyVec<T> uses std::alloc with Layout::array, NonNull<T>, ptr::write/read, ptr::copy for overlapping moves, and Drop that drops exactly len elements and frees the block once.
  • PhantomData<T> expresses ownership; PhantomData<&'a T> expresses a borrow in an iterator made of raw pointers.
  • A queue with head and tail pointers is easy with Box::into_raw/Box::from_raw, as long as tail is reset when the list empties and Drop is iterative.
  • Keep unsafe small, hide it behind a safe API, and make misuse impossible rather than documented.
  • Count constructions and drops to find leaks and double drops, and run the tests under Miri to catch the undefined behavior that counters cannot see.

Next: Embedded, no_std and WebAssembly