The Borrow Checker

I have written mostly C and C++ as long as I have programmed.

However, as I have been experimenting with Rust lately, I have gained the opinion that it is undeniable that the language does have some features that are a great help in reducing the developer’s cognitive load by offloading some safety enforcements to the compiler. Most of these safety measures are enforced by the compiler through the in-built (and notorious) Borrow Checker.

In simple words, the Borrow Checker is an XOR: it enforces that any entity in the program either be mutable or be aliasable. This means, at a very fundamental level, that the compiler now has additional scope of optimization, because it does not have to assume that a block of memory could be aliased under another pointer, like a C or C++ compiler usually would.

The Borrow Checker also enforces the notion of Lifetimes of objects. The basic idea is that if I were to construct some object (let’s call it A) from a non-owning reference to some other object (which we shall call B) that was live at the time of construction of A, then A should not outlive B, because in that case A would basically have a reference to an object that has been freed from memory.

The thing is, when I first started learning Rust, I had an incredibly hard time with it. Most of the tutorials I looked at, or the videos I saw on YouTube, assumed I was familiar with the whole Rust standard library and would use these super-high-level abstractions that would make it extremely hard to follow what was actually happening.

Coming from a C-based pointers-are-memory and everything-is-unsafe model, I was looking for something that could explain to me how unsafe code could be made safer in Rust, so I worked out a few snippets on my own after going through implementations in the Rust standard library. And that, is what this post is all about.

In the following sections, we will deliberately use unsafe Rust code to create a use-after-free condition, then evolve the faulty code so that the compiler understands the lifetimes of all related objects and compilation fails in case an object on which another object is dependent does not live long enough.

Unsafe Rust: Raw Pointers and Use-After-Free

The Rust compiler usually has no notion of what a raw pointer is tethered to. The compiler cannot track its lifetime or perform bounds checking when it is indexed. Basically, a raw pointer is the definition of unsafe in Rust.

To demonstrate a classic use-after-free hazard, let’s first construct a struct that holds a pointer, and its length (basically a simple fat-pointer). Then, to overload the [] operator so we can directly index into the memory, we shall implement the Index trait for the struct, and then write a simple assertion just to check if our implementation is correct.

Let’s call this struct DataBuffer.

1
2
3
4

struct DataBuffer {
    data: *const f32,
    length: usize,
}

The member data is a const raw pointer to memory of type f32.

Let us implement a static method called new(...) on this struct that takes a non-owning reference to a slice of 1-D data of type f32 and constructs a DataBuffer from it.

1
2
3
4
5
6
7
8

impl DataBuffer {
    fn new(sl: &[f32]) -> Self {
        Self {
            data: sl.as_ptr(),
            length: sl.len(),
        }
    }
}

The function, as I mentioned above, takes a reference to a slice, then extracts the pointer by calling the method as_ptr() on it. The method constructs a DataBuffer and then returns it.

The thing to note here is, the original vector from which this slice, which the new() method accepted, was constructed, is still owned by its original owner who passed it into the new() method.

If I were to clone the whole thing, the concept of lifetimes would never arise here, because the compiler would move the cloned memory into the new DataBuffer object and it would become the owner of that memory. But that would also mean we could kiss performance goodbye, so here we are.

We’ll now complete the basics and implement Index for DataBuffer so we can index into it.

1
2
3
4
5
6
7

impl Index<usize> for DataBuffer {
    type Output = f32;
    fn index(&self, i: usize) -> &Self::Output {
        assert!(i < self.length);
        unsafe { &*self.data.add(i) } 
    } 
}

There are a couple things to note here. First is the assertion. We noted that the compiler does not do bounds checking for raw pointers, so it is up to us to guarantee that we do not perform an out-of-bounds access on the array. However, this assert is also horrible for performance, and of course, there are much more elegant solutions in production scenarios.

The other thing to note here is the use of unsafe when dereferencing the pointer. Rust treats the dereference as unsafe, but not the creation of the pointer. That means that every time you deref a raw pointer, it has to be wrapped in an unsafe block. We offset the pointer by the required index, dereference it, then borrow and return the value.

It is time to write a main function and compile the code so we can see if it works.

1
2
3
4
5

fn main() {
    let buf = vec![0.0, 1.0, 2.0, 3.0];
    let dbuffer = DataBuffer::new(&buf);
    assert_eq!(3.0, dbuffer[3]);
}

On running, we should see the code compile fine and the assertion pass.

1
2
3

Compiling playground v0.0.1 (/playground)
 Finished dev profile [unoptimized + debuginfo] target(s) in 0.71s
  Running target/debug/playground

Now let’s spice things up :)

We rewrite the main function, but now we declare the variable dbuffer as mutable so we can overwrite it. We now overwrite it in a scope inside the main function, in which we also re-declare the original vector we called buf from which dbuffer was created.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

fn main() {
    let buf = vec![0.0, 1.0, 2.0, 3.0];

    // dbuffer is now mutable.
    let mut dbuffer = DataBuffer::new(&buf);

    // And here is the scope. Cool thing is, buf
    // will be freed from memory the moment this
    // scope goes OUT of scope.
    {
        // Re-declare buf.
        let buf = vec![0.0, 1.0, 2.0, 3.0];
        // Now overwrite dbuffer to create it
        // from the new buf created in this scope.
        dbuffer = DataBuffer::new(&buf);
    }

    assert_eq!(3.0, dbuffer[3]);
}

See what happened here? We forced a classic use-after-free! At the end of the scope inside the main function (in which buf was re-declared), the memory associated with buf will be dropped. However, the variable dbuffer which holds a raw pointer to that memory is still live. And that means we have now got a dangling pointer.

And that is apparent when we run the code and hit the assertion. The safety guarantees of Rust fail, because of course we asked for it by playing with raw pointers.

1
2
3
4
5
6
7
8

Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.70s
     Running `target/debug/playground`

thread 'main' (13) panicked at src/main.rs:90:5:
assertion `left == right` failed
  left: 3.0
 right: 2.0701483e-19
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Now here is the thing: How do we use the compiler to fix this? Which brings us to…

Lifetimes

Rust allows the developer to syntactically relate the lifetimes of variables in the code. This is a very interesting feature indeed, and we shall now modify our definition of the DataBuffer struct to make use of it.

Lifetimes are usually specified with an identifier following an apostrophe (') in definitions and function arguments. Let’s say that we want our struct to live a lifetime of 'a. Note that the letter a can be any other identifier here, it does not really matter.

1
2
3
4

struct DataBuffer<'a> {
    data: *const f32,
    length: usize,
}

We introduced the lifetime in the definition of DataBuffer. The same is required for the impl block.

1
2
3
4
5
6
7
8

impl<'a> DataBuffer<'a> {
    fn new(sl: &'a [f32]) -> Self {
        Self {
            data: sl.as_ptr(),
            length: sl.len(),
        }
    }
}

This is where the compiler actually enforces the lifetime constraints. We wanted DataBuffer to have a lifetime of 'a, but that does not have a significance on its own. To give it meaning, we also tell the compiler that this is also how long the underlying reference from which we construct the struct will live.

This is done by passing in the lifetime in the function argument to new(...) as sl: &'a [f32]. This tells the compiler that DataBuffer cannot outlive the reference, because we explicitly told it to enforce the same lifetimes on both of them.

In the implementation of the Index trait we just introduce an anonymous lifetime and let the compiler figure it out for us.

1
2
3
4
5
6
7
8

impl Index<usize> for DataBuffer<'_>
{
    type Output = f32;
    fn index(&self, i: usize) -> &Self::Output {
        assert!(i < self.length);
        unsafe { &*self.data.add(i) }
    }
}

But here’s the catch. When you run the compiler on this code, it throws an error.

1
2
3
4
5
6
7

error[E0392]: lifetime parameter `'a` is never used
  --> src/main.rs:50:19
   |
50 | struct DataBuffer<'a> {
   |                   ^^ unused lifetime parameter
   |
   = help: consider removing `'a`, referring to it in a field, or using a marker such as `PhantomData`

The reason for the error is apparent from the error message. We introduced the lifetime parameter in the struct definition, but none of its members make use of the lifetime. The compiler suggests we either remove it or make use of the marker PhantomData. Removing it defeats our purpose, but, as we shall see, PhantomData is exactly what we need.

PhantomData is an interesting feature of Rust. It is a zero-sized entity that is optimized away by the compiler and has no effect on runtime. Its only use is that of a marker. We insert a member of the PhantomData type into our struct, so that the compiler sees that our struct indeed binds to the lifetime we are specifying.

The definitions change a little bit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

use std::marker::PhantomData;

struct DataBuffer<'a> {
    data: *const f32,
    length: usize,
    _marker: PhantomData<&'a f32>,

}

impl<'a> DataBuffer<'a> {
    fn new(sl: &'a [f32]) -> Self {
        Self {
            data: sl.as_ptr(),
            length: sl.len(),
            _marker: PhantomData,
        }
    }
}

We just added a new member of type PhantomData into the struct and initialized it as part of the construction of DataBuffer.

The &'a inside the signature of _marker is what does the binding work: it tells the compiler that this struct logically borrows data for lifetime 'a even though no member explicitly binds to it.

And that is pretty much all. For the exact same main function we had above, we should now see compilation fail!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

error[E0597]: `buf` does not live long enough
  --> src/main.rs:90:35
   |
87 |         let buf = vec![0.0, 1.0, 2.0, 3.0];
   |             --- binding `buf` declared here
...
90 |         dbuffer = DataBuffer::new(&buf);
   |                                   ^^^^ borrowed value does not live long enough
91 |     }
   |     - `buf` dropped here while still borrowed
92 |
93 |     assert_eq!(3.0, dbuffer[3]);
   |                     ------- borrow later used here

This marker pattern is actually a common Rust idiom that is used all over the Rust standard library, and many a times what you see as Rust safety guarantees against use-after-free hazards is this exact idiom in action.

Conclusion

The C compiler trusts you. It will very lovingly saw off your fingers if you order it to. The Rust compiler is reluctant to do that - so it gives you some options to free it from the guilt of the crime.