Motivation for unsafe Rust: Uninitialized memory

In this chapter, you will learn about the motivation behind the unsafe feature of Rust using the concept of uninitialized memory, something that is very familiar to C programmers. It is not the only motivation for unsafe Rust, in the next chapter we will talk about interfacing with C functions which are unsafe by default, but it fits nicely within the context of this book chapter about the role of memory in systems programming. You will learn about the nitty-gritty details of how to implement the Vec<T> type, one of the most important container types in the Rust standard library, and learn why unsafe is required to implement an efficient Vec<T>.

unsafe Rust: When safety is not an option

First and foremost, unsafe is a keyword in Rust. It applies to functions as well as to scopes:

#![allow(unused)]
fn main() {
unsafe fn foo() {
    // Do lots of unsafe things here
}

fn bar() {
    let data = 42;
    // Do something unsafe here:
    unsafe {
        // ?
    }
}
}

When we use the unsafe keyword, we tell the compiler: "Disable many of the typical safety features while checking the following code". What safety features? Here is a (non-exhaustive) list:

• Allow calling other functions marked as unsafe
• Allow the usage of raw pointers, which have no lifetimes attached to them
• Allow accessing and mutating static mut variables
• Allow interfacing with externally linked C functions (which are unsafe by default)

Pointers are perhaps the biggest feature of unsafe Rust. They are a deliberate step back from the borrows+lifetimes type checking system that we spent so much time learning about. There are good reasons to use them, as we will see shortly, and their syntax is similar to what you might be used to from C and C++. Because raw pointers allow memory-unsafety (out-of-bounds accesses, race conditions etc.), the safety of code using raw pointers cannot always be guaranteed. If you encounter an unsafe function, you can think of it as a function for which the compiler cannot guarantee that it is always safe to use: It might corrupt memory, produce a race condition, or simply result in undefined behavior. A key observation is that this only happens if you use the function incorrectly! A function that always introduces undefined behavior is not very useful, so instead every unsafe function will have a set of safety guarantees that the caller must uphold, and which are not enforced by the compiler.

Let's look at an example:

unsafe fn front_unchecked<T>(array: *const T) -> T {
    unsafe {
        std::ptr::read(array)
    }
}

fn main() {
    let arr = [42; 4];
    println!("{}", unsafe { front_unchecked(arr.as_ptr())});
}

This unsafe function takes a pointer to an array and returns the first element of that array. This is kind of like Vec::<T>::front, but with no bounds checking performed, and without any moves. It uses the unsafe function std::ptr::read, which has the following signature: unsafe fn read<T>(src: *const T) -> T. It implements the same behavior as the dereferencing operator * in C/C++. Calling front_unchecked requires a pointer to an array (or a single element), which we can obtain from a Rust slice using as_ptr.

Ensuring safety when working with unsafe code

A big question when working with unsafe code is: "Is this usage of unsafe actually safe?" If we use an unsafe function in a way that violates its safety guarantees, our program contains a bug. Since the safety guarantees are not encoded in the type system, they are not checked automatically, meaning we have to do the check manually ourselves by reading the documentation of the unsafe function. This makes working with unsafe Rust much harder than with safe Rust!

Let's look at our front_unchecked function and see if its usage of std::ptr::read is safe or not. As a properly documented unsafe function, std::ptr::read has a Safety section, which reads:

Behavior is undefined if any of the following conditions are violated:
- src must be valid for reads.
- src must be properly aligned. Use read_unaligned if this is not the case.
- src must point to a properly initialized value of type T.
Note that even if T has size 0, the pointer must be properly aligned.

If you start to work with unsafe Rust code, you will see that it sometimes feels like going down a rabbit hole of tricky conditions. In this case, the innocent statement src must be valid for reads links to the general safety rules of the std::ptr module, which contain one crucial statement: The precise rules for validity are not determined yet. It continues with a list of things that are allowed and not allowed, but the fact that there is no clear rule set for pointer validity is one of the reasons that unsafe Rust is tricky to get right.

For now, let's stick with a definition for validity that simply means the memory is properly allocated, the pointer points within that memory, and there are no concurrent writes while we read from the pointer. On top of that come the other two requirements from std::ptr::read, namely proper alignment and proper initialization. The neat thing with our front_unchecked function is that we can simply pass these safety requirements onto the caller, as we cannot determine all these invariants from within the function body of front_unchecked. After all, we do not know where the pointer comes from that is passed to front_unchecked! But this is not where it ends. Try to answer the following question for yourself before reading on:

We can easily create a Rust program that has a memory safety issue using our front_unchecked function by exploiting a subtle requirement of this function:

fn main() {
    let arr2 = [vec![1,2,3,4,5,6]; 1];
    println!("{:?}", unsafe { read_first(arr2.as_ptr())});
    println!("{:?}", arr2[0]);
}

Running this program in debug mode will result in a double-free error. This is exactly the kind of memory error that Rust aims to prevent in the first place. This is the price of using unsafe! We will see shortly what we get for paying this price, but first we have to figure out what exactly went wrong here.

Recall that Rust is move-by-default, whereas C++ was copy-by-default? You might have noticed that std::ptr::read creates a copy of the value pointed to by its argument. The signature of std::ptr::read is *const T -> T, not *const T -> &T after all! What happens is that a simple bitwise copy is created, but we never specified that the type T supports bitwise copies. Since we read a non-Copy type (Vec<i32>) using std::ptr::read, we end up with two vectors both pointing to the same dynamically allocated array internally. Once the first Vec<i32> goes out of scope (after the first println! statement), the underlying memory has been freed. When the second Vec<i32> goes out of scope (the one inside arr2), this triggers the double-free error!

We can fix this in one of two ways:

• Either we put "the type T must be safe for bitwise copies" into the # Safety section of the function documentation
• Or we simply require that T: Copy in the signature

Note that it is the rare exception that safety guarantees of unsafe functions can be encoded in the type system. If we could encode all safety guarantees in the type system, there would be no need for unsafe after all!

A more useful example: Implementing Vec<T>

The previous example was somewhat contrived. It was meant to illustrate how we work with unsafe code, but its usage is limited. The only benefit over using something like std::slice::first is that is skips the bounds check and returns T instead of Option<&T>. As promised, now is the time to look at a more useful example, namely the implementation of Vec<T> for arbitrary types.

Recall our first attempt at defining Vec<T> in chapter 3.3.6:

#![allow(unused)]
fn main() {
struct CustomVec<T: Copy> {
    data: Box<[T]>,
    size: usize,
    capacity: usize,
}
}

There are two problems with this approach:

• It requires that T: Copy
• We only deferred the difficult problem of handling the dynamic array to another standard library type Box<[T]>

There is a third problem that will become apparent once we try to implement the grow function that grows the internal array whenever more space is needed. A simple strategy for vector growth is to start with an empty array, on the first allocation use a small number of elements, for example 4, and then double the size whenever the array is full and more space is required. Here is an attempt to implement this algorithm in Rust:

#![allow(unused)]
fn main() {
impl<T: Copy> CustomVec<T> {
    fn grow(&mut self) {
        const FIRST_ALLOC_LENGTH: usize = 4;
        let new_capacity = FIRST_ALLOC_LENGTH.max(self.capacity * 2);
        let mut new_array = Self::alloc_dynamic_array(self.capacity * 2);
        if self.capacity > 0 {
            new_array[..self.capacity].copy_from_slice(&self.data);
        }
        self.data = new_array;
        self.capacity = new_capacity;
    }
}
}

We use a magic function Self::alloc_dynamic_array with the signature usize -> Box<[T]> that allocates a Box<[T]> for us, more on that in a moment. First, verify that the algorithm is correct: We allocate a new array that is either twice the previous size, or has a small initial size in case we never allocated (self.capacity is zero). Then, if we had a previous allocation, we copy all elements from the old array over to the new array and overwrite self.data. This will release the dynamic memory for the old array if there was one, due to the way Box<[T]> works. Lastly, we update our capacity.

Notice that this whole function uses zero unsafe! Alas, this is only true because we hid all the nasty details inside Self::alloc_dynamic_array:

#![allow(unused)]
fn main() {
impl<T: Copy> CustomVec<T> {
    fn alloc_dynamic_array(capacity: usize) -> Box<[T]> {
        let arr = unsafe {
            std::alloc::alloc(
                Layout::array::<T>(capacity).expect("Failed to allocate new dynamic array"),
            )
        };
        unsafe {
            let slice = std::slice::from_raw_parts_mut(arr as *mut T, capacity);
            Box::from_raw(slice as *mut [T])
        }
    }
}
}

Here we see lots of unsafe code, and a bunch of new functions. Dynamic memory allocations are supported by the Rust standard library through the std::alloc module. The way it works is we first have to create a memory layout using the Layout type. In our case we want an array of capacity elements of T, so Layout::array is the function we need. Then we call std::alloc::alloc with this layout. The layout creation part is safe, but it can fail, for brevity we simply .expect that it doesn't. The allocation itself is the unsafe part, so we have to read the documentation. The only thing we care about is this line here:

layout must have non-zero size. Attempting to allocate for a zero-sized layout may result in undefined behavior.

Since we already talked about memory layouts try working through the following exercise on your own before reading on:

#![allow(unused)]
fn main() {
#[test]
fn vec_with_zero_sized_type() {
    let mut v = CustomVec::new();
    v.push(());
}
}

Before we move on to fix the issues with our grow function, we still have to go over the other unsafe code, namely std::slice::from_raw_parts_mut. We use this function to turn our raw pointer to a dynamically-sized array into the Rust builtin slice type. Recall that a slice is a fat pointer containing both the memory address and the number of elements in the array. We have both pieces of information available to use, so we can create a slice from them. There are many safety requirements for std::slice::from_raw_parts_mut, you are encouraged to have a look at them as we won't list them all here. Informally speaking, they require that we pass in a correctly initialized array of the correct size, coming from a single memory allocation, with the additional requirement that the pointer is the sole owner and reference to the memory. This last point allows the borrow checker to reason about the lifetime of the memory, and ensure the rule of one for the mutable borrow that is returned.

The last unsafe function we use is Box::from_raw, which has an even longer list of safety requirements. We turn our slice into a Box<[T]> simply because we want to utilize the automatic cleanup that Box provides. We need to both call the destructor (Drop::drop) of every element within the slice, as well as deallocate the memory of the slice itself. We have to do the gymnastics of first creating a mutable borrow to a slice of T (&mut [T]) and then convert that back into a pointer to a slice (*mut [T]) and pass that into Box::from_raw so that the Box correctly wraps a dynamic array of elements. If we had instead converted the *mut u8 pointer obtained from std::alloc::alloc into a *mut T and passed that into Box::from_raw, we would have ended up with a Box<T> pointing to a single element! Notice that Rust has different semantics even for raw pointers: We can clearly differentiate between a pointer to a single element (*mut T) and a pointer to an array of elements (*mut [T]).

Fixing issues with CustomVec::grow

We saw that we cannot rely on std::alloc::alloc to work correctly for zero-sized types, as it may result in undefined behavior. If you read the documentation for std::slice::from_raw_parts_mut carefully, you might have noticed that it offers a solution for working with arrays of zero-sized types:

data must be non-null and aligned even for zero-length slices or slices of ZSTs. One reason for this is that enum layout optimizations may rely on references (including slices of any length) being aligned and non-null to distinguish them from other data. **You can obtain a pointer that is usable as data for zero-length slices using NonNull::dangling().** (emphasis ours)

The last sentence is the interesting one: For zero-length slices there is something called NonNull::dangling() that we can call to obtain the correct type of pointer. In our case, we have a slightly different requirement---a slice to zero-sized types (ZSTs)---but the idea is similar. The problem that we are trying to solve is that we cannot use std::alloc::alloc for ZSTs, but we still need a pointer to something.

#![allow(unused)]
fn main() {
struct CustomVec<T> {
    data: Box<[T]>,
    size: usize,
    capacity: usize,
}
}

#![allow(unused)]
fn main() {
struct CustomVecZeroSized<T> {
    size: usize,
}
}

NonNull::dangling() is one option for obtaining a pointer that satisfies the memory layout requirements of pointers for usage as slices. In particular, it is not null and it respects alignment even for ZSTs. The NonNull type is interesting: It is a wrapper around a raw mutable pointer *mut T that provides additional guarantees that *mut T does not give. For one, it ensures that the pointer is not null, which can be helpful in various situations that rely on pointers not being null. It also provides something called covariance, which refers to how type conversion propagate to wrapped types. The Rust language documentation on variance has more information if you are interested.

If we try to use NonNull::dangling() instead of std::alloc::alloc for ZSTs, we run into problems unfortunately: Since the dangling pointer does not come from an actual memory allocation, it is illegal to wrap it in a Box<[T]>, as the Drop implementation of the Box would try to deallocate the memory. ThisAnd the fact that Box<[T]> assumes all elements are properly initialized forces us to reconsider the usage of Box<[T]>, which felt like a bit of a cheat anyways given that Box<T> is a type from the Rust standard library and we don't really know how it handles allocation and destruction. So we adjust our CustomVec<T> definition to the following:

#![allow(unused)]
fn main() {
struct CustomVec<T> {
    data: NonNull<T>,
    size: usize,
    capacity: usize,
}
}

Your initial impulse might have been to use NonNull<[T]> instead, however that won't work because slice types don't have a well-known size at compile-time and therefore many of the functions on NonNull that we need are not usable. This is unfortunate as NonNull<T> for a dynamically-sized array does not match the intuition: We have a pointer to an array, not a single element after all! While there are reasons for this, a thorough understanding of them would require a more comprehensive explanation than we can reasonably give in this chapter. For now, we just have to accept this fact.

Before moving on to the implementation of this new CustomVec<T> type, first try to answer the following question:

Creating a new CustomVec<T> looks like this:

#![allow(unused)]
fn main() {
pub fn new() -> Self {
    Self {
        // Zero-sized types take no space, hence in this case we have the maximum possible capacity and never 
        // need to grow!
        capacity: if Layout::new::<T>().size() == 0 {
            usize::MAX
        } else {
            0
        },
        data: NonNull::dangling(),
        size: 0,
    }
}
}

The alloc_dynamic_array function changed quite a bit:

#![allow(unused)]
fn main() {
fn alloc_dynamic_array(capacity: usize) -> NonNull<T> {
    let layout = Layout::array::<T>(capacity).expect("Failed to allocate new dynamic array");
    let arr: *mut u8 = unsafe { std::alloc::alloc(layout) };
    // alloc is allowed to return a null-pointer if there is not enough memory
    if arr.is_null() {
        panic!("Out of memory");
    }
    // At this point we know our allocation succeeded and we have a proper non-null pointer
    // Since alloc returns `*mut u8`, we have to cast to `*mut T`
    unsafe { NonNull::new_unchecked(arr as *mut T) }
}
}

The return type changed, and we explicitly deal with failed allocations, something that we (silently) forgot to do in the previous version of the code! A dangerous property of this code is that we return a pointer to a single element (that is what NonNull<T> means), but we as the implementors know that it actually points to an array of elements! We have to keep that in mind in the rest of the implementation of CustomVec<T>!

Since we have a new return type of alloc_dynamic_array, the grow function changes as well:

#![allow(unused)]
fn main() {
fn grow(&mut self) {
    const FIRST_ALLOC_LENGTH: usize = 4;
    let new_capacity = FIRST_ALLOC_LENGTH.max(self.capacity * 2);
    let new_array: NonNull<T> = Self::alloc_dynamic_array(new_capacity);
    if self.capacity > 0 {
        // This doesn't work anymore because NonNull<T> is NOT a slice!
        // new_array[..self.capacity].copy_from_slice(&self.data);
    }
    self.data = new_array;
    self.capacity = new_capacity;
}
}

We now face the problem of copying the elements from the old array to the new array. Where previously we dealt with the builtin slice type and could use copy_from_slice, this doesn't work anymore with raw pointers such as NonNull<T>. Luckily, there are similar functions such as NonNull::copy_from_nonoverlapping that we can use:

#![allow(unused)]
fn main() {
unsafe {
    new_array.copy_from_nonoverlapping(self.data, self.capacity);
}
}

It copies self.capacity elements from the given memory address (self.data) into self (new_array in our case). The non_overlapping part simply means that the two memory regions do not overlap, which lets the compiler emit more efficient codeNon-overlapping copies in Rust are semantically equivalent to memcpy in C, whereas overlapping copies are equivalent to memmove. The function is unsafe because it performs a bitwise copy of types that might have stricter requirements (such as specific alignment), and the compiler cannot know if the memory pointed to actually contains the given number of elements. Lastly, the non-overlapping property is not checked to keep the code efficient, but accidentally passing in overlapping memory therefore causes undefined behavior. Again, it is crucial that we read the safety section in the documentation.

Before moving on to the interesting functions push and get, we have to remember that we now store a raw pointer to an allocated memory block inside our CustomVec type. This means we have to implement a destructor, which in Rust is done by implementing the Drop trait:

#![allow(unused)]
fn main() {
impl<T> Drop for CustomVec<T> {
    fn drop(&mut self) {
        // 1) Call "Drop" implementation for every element

        // TODO Drop elements implementation

        // 2) Deallocate memory, but only if we are not zero-sized and actually have elements
        if Self::SINGLE_VALUE_LAYOUT.size() == 0 || self.capacity == 0 {
            return;
        }

        // TODO Deallocation implementation
    }
}
}

Drop for CustomVec has to perform the exact same operations as operator delete[] would in C++: First, call the destructor of every element, then deallocate the memory. Deallocation is fairly easy, as there is std::alloc::dealloc:

#![allow(unused)]
fn main() {
unsafe {
    std::alloc::dealloc(
        // dealloc expects a pointer to u8, not to T, so we cast here
        self.data.as_ptr() as *mut u8,
        // dealloc needs the exact layout that we gave to alloc
        Layout::array::<T>(self.capacity).expect("Failed to create Layout for array of T"),
    );
}
}

Concerning safety, we need to make sure that the pointer points to an allocation from the same allocator, and that we pass in the exact same Layout as we did to std::alloc::alloc. Both are true in our case.

Now what about calling the destructor of every element? As the Rust documentation tells us, we cannot call Drop::drop ourselves! There is std::mem::drop, which simply lets an instance of a type go out of scope, therefore invoking the destructor, but this is out of the question in our case, as multiple instances sit within a dynamically allocated memory block. One way to do that is to move every element out of the dynamic array, manually drop it, and then simply deallocate the whole array, as it now consists entirely of moved or uninitialized elements:

#![allow(unused)]
fn main() {
unsafe {
    for index in 0..self.size {
        let element = self.data.add(index).read();
        drop(element);
    }

    // Then deallocate self.data
    // ...
}
}

This works, but is less efficient than it can be: The ptr::read function performs a bitwise copy of each element, which then immediately gets dropped. Compared to a (fictional) direct function call of Drop::drop, the resulting assembly code of the ptr::read solution will contain additional instructions to do the bitwise copy into a variable on the stack. A more efficient (and elegant) solution is to use a special function called std::ptr::drop_in_place:

#![allow(unused)]
fn main() {
unsafe {
    let valid_slice = std::slice::from_raw_parts_mut(self.data.as_ptr(), self.size);
    std::ptr::drop_in_place(valid_slice);
}
}

Reading the documentation of std::ptr::drop_in_place is insightful as it points out edge-cases that we might not have considered (such as dropping unsized types).

Writing and reading using push and get

To make our CustomVec usable, we need ways to insert elements and access existing elements. Let's start with the more difficult implementation of push first. The algorithm looks like this:

#![allow(unused)]
fn main() {
fn push(&mut self, element: T) {
    // 1) Is there no space left? If so, grow() first
    // 2) Write the element to the next free position
    // 3) Increment size
}
}

Bullet points 1) and 3) are trivial, but 2) requires some thought. Recall that we store our data through a NonNull<T>, which is not a Rust slice or something that we can index using the [] operator, but instead a raw pointer. Similar to C/C++, we need to use pointer arithmetic to obtain a pointer to the correct memory address and then write our element into that address. Luckily for us, there is std::ptr::write which does the second part:

#![allow(unused)]
fn main() {
fn push(&mut self, element: T) {
    if self.size == self.capacity {
        self.grow();
    }

    let head = self.data.as_ptr();
    unsafe {
        head.add(self.size).write(element);
    }
    self.size += 1;
}
}

It is worth looking into std::ptr::write because it performs an interesting operation with regard to the value semantics of the Rust language. We already learned that Rust is move-by-default, and we saw that a move is identical to a bitwise copy in many cases. What is different is that moved-from values cease to exist and therefore require no destructor call. A quick recap:

fn consume(data: String) {}

fn main() {
    let s = String::new("Strings require Drop::drop calls!");
    consume(s);
    // println!("{s}"); // Does not compile because `s` has been moved
}   // Instead of going out of scope at the end of `main`, `s` is already out of scope
    // So no destructor call at the end of `main` for `s`!

It is important to understand that the memory of the local variable s on the stack is unaffected by the move! Within the rules of the Rust language, you are not allowed to reference that memory anymore after the s has been moved, but on the machine level, it is perfectly valid if the stack space gets reclaimed only after main exits and not right when s is moved into consume!

The situation is similar for our std::ptr::write call: We copy the bits that make up our element into the dynamic array at the correct position and also mark the variable element as "has been moved". If we didn't do that second part we would risk a double-free, because the destructor of element would run at the end of push and then again once our CustomVec gets destroyed! It is for that reason that std::ptr::write does not call the destructor of its argument! Take a look at the following visualization together with the relevant code inside grow:

#![allow(unused)]
fn main() {
fn push(&mut self, element: T) {
    // (1)
    // ...
    let head = self.data.as_ptr();
    unsafe {
        head.add(self.size).write(element); // (2) and (3)
    }
    // ...
}
}

Another important point to keep in mind when using std::ptr::write is that it also does not call the destructor of the current value at the memory location! In our case this is fine because our CustomVec guarantees that when we call push, the memory address at which we push contains uninitialized memory. Therefore no previous instance of T is overwritten! The fact that we work with uninitialized memory is one of the main reason why we needed unsafe in the first place: Within safe Rust, you will never encounter uninitialized memory. It is also the reason why the implementation of CustomVec from chapter 3.3.6 required T: Copy and yet still is subtly wrong: We convert uninitialized memory to a slice of T, but this is not allowed in Rust. The correct way to point to uninitialized value is through the MaybeUninit<T> type.

get luckily is a bit simpler:

#![allow(unused)]
fn main() {
pub fn get(&self, index: usize) -> Option<&T> {
    // Bounds checking so that we don't access uninitialized memory
    if index >= self.size {
        return None;
    } 
    // Go from a pointer to the element to a Rust borrow. This is unsafe as the compiler can't 
    // guarantee that the pointer has the same semantics as a reference (proper alignment, memory 
    // is initialized, there are not mutable borrows to the memory etc.)
    unsafe {
        let element = self.data.add(index).as_ref();
        Some(element)
    }
}
}

We still don't get away without using unsafe, as going from a pointer to a borrow is a dangerous operation.

#![allow(unused)]
fn main() {
/// Obtain a reference to the element at `index` without bounds checking
/// # Safety
/// `index` must be within the bounds of the vector
pub unsafe fn get_unchecked(&self, index: usize) -> &T {
    self.data.add(index).as_ref()
}
}

Recap

With this, we wrote our first low-level collection in Rust that is efficient and correctly uses unsafe code!

Try to answer the following questions for yourself:

• What problem does unsafe Rust solve?
• How can we make sure that we correctly use an unsafe function?
• What does std::ptr::write do with its argument?
• What was the purpose of using NonNull::dangling() in the constructor of CustomVec<T>?