In this article, I hope to introduce the borrow checking style of managing memory, with a general point of view, hopefully also explaining the Rust borrow checker in the process.
First, what is memory safety? A memory safe program is one that does not contain:
Note: In this article, I consider a double free to be a subset of use after free.
A memory leak occurs when some data becomes inaccessible (without special means), and the data wasn't made available for further allocation. Example:
void foo() {
uint64_t* bar = malloc(sizeof(uint64_t));
// variable goes out of scope but never got freed
}
int main() {
foo(); // leaks 8 bytes of memory
}
A use after free occurs when some data is made available for further allocation while still having a variable refer to it. Example:
int main() {
uint64_t* bar = malloc(sizeof(uint64_t));
free(bar);
printf("%llu\n", bar);
}
The former results in wasting memory, potentially running out of it, and the latter results in using garbage data, potentially a segmentation fault if the data makes some program read outside of its allowed area.
There are three main approaches to dealing with memory safety.
Garbage Collection is a sort of delayed / lazy form of runtime reference counting. This results in less consistent overhead at the cost of occasional spikes in usage.
Each comes with its own set of flaws.
Languages like Rust solve the expressiveness issue by having something like unsafe, which lets the programmer do whatever they want, promising that what they are doing is actually safe. There are some issues with that approach of course, and some argue that Rust could provide more guarantees in unsafe while remaining useful, however that is out of scope for this article.
The main benefits of borrow checking is that it does not require a runtime like GC, and guarantees memory safety, unlike manual memory management.
Let's define a very small language, that just has variables and functions. Everything is heap-allocated for explanatory purposes, however in a real language one would only apply this to actually heap allocated objects, since stack allocated objects mostly don't need any sort of special memory management. We do not have any globals right now, nor any complex structures like arrays, objects or structs.
foo(a, b) {
return a + b;
}
main() {
foo(1, 2);
}
Now, let's add a constraint. Each variable can only be used once. This is called linear typing. If we have no builtins, we cannot construct any valid program that terminates:
foo(a) {
// What do we call outside of bar?
// Calling bar will result in infinite recursion,
// and the program will never terminate...
}
bar(a) {
foo(a);
}
main() {
a = 2;
foo(a);
}
Let's add a single builtin, drop(). drop() is sort of like free in C:
foo(a) {
drop(a);
}
main() {
a = 2;
foo(a);
}
We can now make a program that terminates! But it is quite useless, isn't it?
First, some terminology change. Instead of saying we use a variable, let's say we move it.
We can either move a variable in the same scope (renaming, b = a), move it into a "child" scope (calling, foo(a)), or move it from a "child" scope into a "parent" scope (returning, return a).
Now, we can introduce references. A reference to a variable can be taken using the & prefix unary operator:
main() {
a = 2;
print(&a);
print(&a);
drop(a);
}
A reference has those three rules:
drop() on a reference is a no-op.The first rule avoids use after frees:
main() {
a = 2;
b = &a;
drop(a);
print(b); // use after free, can print garbage!
}
The second rule makes references actually useful, and does not violate any previous rules, because:
drop() a no-op ensures that even if we do try to free it, it does not invalidate any other references.The third rule is as described above, as defining it to free what it is referencing would cause it to allow use-after-frees.
Let's define what a valid reference means. There are quite a few approaches one can take. The simplest one is to simply check if there are any references mentioned no matter the control flow after a variable could reach a move. One could also do various magic with flow, refinement or even dependent typing, but that's outside of the scope of this article.
With this, we get quite a powerful language. It is fully memory safe, however still very expressive.
One can automatically insert drop() when a variable hasn't been moved at the end of its scope.
This comes with its own set of challenges, such as the compiler "tripping over itself" and one needing to "help" it with temporary variables to make the scope clearer.
Rust has this issue if you try to reference a value not owned by a variable. Solving it is quite complex, so Rust hasn't bothered.
As you might've noticed, we do not have any complex structures that can contain references. This is because those require lifetimes. A lifetime is a description on a complex variable that it contains references to one or more variables. For example:
main() {
a = 1;
b = 2;
foo = [&a, &b];
}
foo now contains the information that it references the variables a and b: foo<'a, 'b>. foo is now to be treated as a reference to both a and b, such as not allowing a and b to be moved if foo is ever used.
I hope this somewhat brief overview of this approach to memory management is helpful. Do note that Rust doesn't actually do things in exactly the same way, for example they use affine typing (use a variable 1 or 0 times) and insert drop() in a slightly different way. There are other differences, which I didn't go into here as this article is not meant to focus on Rust in particular.