Allocation and a growable buffer

A Vec is a pointer, a length and a capacity, and behind those three words is a call to the allocator. This lesson makes the same calls by hand: one block for one value, then a buffer that doubles when it is full and copies its elements into the new block.

Every function here is in std::alloc and every call is unsafe, because the compiler no longer checks the three things that matter: the layout matches the allocation, the memory is initialised, and nothing else uses it. The last section is the error for a call outside the block.

One allocation

Layout describes an allocation: a size and an alignment. alloc returns a pointer to that many bytes, and dealloc takes the same layout back. Writing and reading through the pointer is the unsafe part.

The program allocates room for one integer, writes ninety-nine and reads it back. The address is freed with the layout it was allocated with.

use std::alloc::{alloc, dealloc, Layout}; fn main() { let layout = Layout::new::<u32>(); unsafe { let pointer = alloc(layout) as *mut u32; pointer.write(99); println!("{}", *pointer); dealloc(pointer as *mut u8, layout); } }

rustc --edition 2024 alloc_one.rs
./alloc_one

99

The cast from *mut u8 to *mut u32 is where the type comes back, and it is only valid because the layout asked for the alignment of u32. A layout of one byte with a cast to u32 would be misaligned and undefined behaviour. The lesson on layout gives the numbers.

A buffer that grows

The buffer keeps the pointer, the length and the capacity. When the length reaches the capacity, a new block of twice the size is allocated, the old elements are copied into it, and the old block is freed with its own layout.

The program starts with room for two elements and pushes three, so one growth happens. The print shows the length, the new capacity and the second element.

use std::alloc::{alloc, dealloc, Layout}; use std::ptr; struct Buffer { pointer: *mut i32, len: usize, capacity: usize, } impl Buffer { fn new(capacity: usize) -> Self { let layout = Layout::array::<i32>(capacity).unwrap(); let pointer = unsafe { alloc(layout) as *mut i32 }; Buffer { pointer, len: 0, capacity } } fn push(&mut self, value: i32) { if self.len == self.capacity { let new_capacity = self.capacity * 2; let new_layout = Layout::array::<i32>(new_capacity).unwrap(); let new_pointer = unsafe { alloc(new_layout) as *mut i32 }; unsafe { ptr::copy_nonoverlapping(self.pointer, new_pointer, self.len); dealloc(self.pointer as *mut u8, Layout::array::<i32>(self.capacity).unwrap()); } self.pointer = new_pointer; self.capacity = new_capacity; } unsafe { self.pointer.add(self.len).write(value) }; self.len += 1; } fn get(&self, index: usize) -> Option<i32> { if index < self.len { Some(unsafe { *self.pointer.add(index) }) } else { None } } } impl Drop for Buffer { fn drop(&mut self) { unsafe { dealloc(self.pointer as *mut u8, Layout::array::<i32>(self.capacity).unwrap()); } println!("released {} slots", self.capacity); } } fn main() { let mut buffer = Buffer::new(2); for value in [10, 20, 30] { buffer.push(value); } println!("{} {} {}", buffer.len, buffer.capacity, buffer.get(1).unwrap()); }

rustc --edition 2024 buffer.rs
./buffer

3 4 20
released 4 slots

The third push allocates four slots, copies two and frees the block of two, which is the sequence every growable container performs. The destructor frees the last block, and the layout of that block is the capacity of four, not the length of three: a mismatch between the two is the most common bug in code like this and the allocator cannot detect it. The lesson on Vec uses the container that already does all of this.

The copy is copy_nonoverlapping, which promises the two blocks do not overlap and is therefore allowed to use the widest move the processor has. The overlap-safe copy is the one for shifting elements inside one block, as a Vec::remove does. A buffer like this one can also be handed back to the standard library with Vec::from_raw_parts, which takes the same three words and frees the block in its own destructor.

Zero size and the empty buffer

An allocation of zero bytes is not allowed, and a layout of size zero is a legal value that must never reach alloc. A container with no elements therefore holds a dangling, non-null pointer and asks for nothing, which is what Vec::new does.

The program prints the size of an empty array layout, the size and the alignment of one integer, and the capacity of a new vector.

use std::alloc::Layout; fn main() { let empty = Layout::array::<i32>(0).unwrap(); let one = Layout::new::<i32>(); let vector: Vec<i32> = Vec::new(); println!("{} {} {}", empty.size(), one.size(), one.align()); println!("{}", vector.capacity()); }

rustc --edition 2024 zero.rs
./zero

0 4 4
0

The empty layout has size zero and must not be allocated; the vector reports a capacity of zero and has not touched the allocator yet. A buffer type that always allocates at construction wastes one call, and one that passes a zero-size layout to alloc is undefined behaviour even when the pointer is never used.

The same job with Vec

The safe version of the buffer is four lines, because the container keeps the three words and the allocator calls inside itself. The program builds the same three values and prints the same facts.

The output matches the hand-written buffer without the release line: the vector frees its block in its own destructor, silently.

fn main() { let mut values = Vec::with_capacity(2); for value in [10, 20, 30] { values.push(value); } println!("{} {} {}", values.len(), values.capacity(), values[1]); }

rustc --edition 2024 with_vec.rs
./with_vec

3 4 20

The capacity is four because the standard library grows by doubling, exactly like the hand-written version. Writing the buffer by hand is a lesson and not a recommendation: the only reason to own the allocation is a layout the container does not cover, and even then the next lesson puts the policy in an allocator instead of in the container.

An allocation outside the block

alloc is an unsafe function, so the call needs the block even though nothing is written yet. The compiler reports E0133 at the call, and the note points at the documentation that states the requirements.

The program asks for one integer in safe code. The compiler stops at the call.

use std::alloc::{alloc, Layout}; fn main() { let layout = Layout::new::<u32>(); let pointer = alloc(layout); println!("{pointer:?}"); }

rustc --edition 2024 alloc_err.rs

error[E0133]: call to unsafe function `std::alloc::alloc` is unsafe and requires unsafe block
--> alloc_err.rs:5:19
|
5 | let pointer = alloc(layout);
| ^^^^^^^^^^^^^ call to unsafe function
|
= note: consult the function's documentation for information on how to avoid undefined behavior

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0133`.

The path in the message is the function as it is exported, std::alloc::alloc, which is the name the documentation uses. A wrapper that checks the capacity and the layout once, and keeps the unsafe calls in one place, is the shape a library uses; the unsafe lesson calls that a sound abstraction.

Exercises

1. Add a pop to the buffer that returns the last value and leaves it uninitialised.
2. Allocate an array of ten u64 with Layout::array, fill it and free it with the same layout.
3. Print capacity after each push of the vector version and compare the growth with the hand-written one.

The code on this page was built with rustc 1.96.1 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev