Rust Memory Management - An Introduction
Created: 2024-03-10
Introduction
Anyone who knows Rust knows that memory management is one of the first topics we need to cover, this is one of Rust's unique selling points.
Rust is a language for writing highly performant software that compiles down to OS binary programs whilst retaining memory safety but without the necessity of a garbage collector. In this article we're going to unpack what this means, why it's important and what effects that might have on you as the end user.
Note that this article won't teach you how to use Rust but it does assume some technical knowledge around programming generally and I will give you the full technical details along the ways. Many things will be explained from the ground up as needed.
By the end of this article you expect to have a high level overview of how Rust does memory management that should make reading the book (a common source for beginners) easier.
First we review manual memory management and garbage collection in other languages so you can see the difference with how Rust does this. We describe the manual memory management approach from traditional C type languages and then we move on to discuss garbage collected languages and the advantages and disadvantages they bring. After this we talk about how Rust does things and then we compare that approach with these other two.
How C does Memory Management
You may not have done much programming in C before or other languages that do manual memory management. We have to first understand the difference between the stack and heap first.
Any program that you run on most operating systems is allocated both a stack and a heap area of memory. Garbage collected languages like Java, C#, Python and JavaScript sometimes hide these kinds of details from the end user, but with C we need to understand these terms to understand memory management there. They're not that complicated and some readers may not have come across these terms before so we go over the basics now.
Aside: I avoided the temptation to say C/C++, traditional C++ also does manual memory management this way but the newer C++ variants I believe have other options now. To avoid alienating the C++ readers I didn't want to draw this comparison as it doesn't matter for this article. In this article I mostly mention C, but a lot of this applies to at least traditional C++ too.
The Stack
The stack is an area of memory that values for variables are pushed onto as they're created and popped off as they're no longer required. Local variables are always created on the stack and once they go out of scope the area of memory is marked as reusable.
Let's demonstrate to make this clear. Let's consider the following simple C program (don't worry if you don't know C, you only need to the rough idea and I'll explain everything you need):
Figure 1: Building and Running the Stack Program
#include <stdio.h>
void my_func(int b) {
b = b + 1;
int a = 42;
printf("a = %d, b = %d\n", a, b);
}
int main() {
int b = 49;
my_func(b);
printf("b = %d\n", b);
return 0;
}
This has a main function that is the entry point of the program. The first
line int b = 49; adds something to the stack that we can refer to with the
variable b in the rest of the function. We then pass the value of b into the
function my_func, this actually adds another variable b onto the top of the
stack with the value 49 also that hides the first b in main until this
function returns. Then we create a new variable a with value 42 and add that
to the top of the stack. If this isn't clear please watch the video in Figure 1
that will explain step by step what's going on here by running it through a step
through debugger.
The Heap
Unfortunately, whilst the stack is fast access and simple, it's only possible when you know the size of the memory you're using. If you want a list of an unknown number of things or that dynamically changes for example, you can't just put them all on the stack, for this we need the heap.
Now to use the heap I need to explicitly say to the OS, "give me some memory on the heap" and then I need to free it when I'm done. We can also do things like resize our heap allocation and the OS will deal with finding a new bit of memory that is suitable. Specifically I do something like the following in C:
#include <stdio.h>
#include <stdlib.h>
int main() {
int *p = (int *)malloc(sizeof(int));
*p = 10;
printf("%d\n", *p);
free(p);
return 0;
}
The first statement creates a pointer p to an integer and we use the libc
malloc function to create space for an integer on the heap (which seems a bit
pointless, you could just do this on the stack, but for demonstration this is
fine). Note that the pointer p still lives on the stack as you need somehow to
be able to access this new heap data. The value pointed to by p (which is is
*p, literally point to the location p points to) is uninitialized to begin
with so we set it to 10 in the next statement, then we print it and finally we
use the free libc function to get the memory back.
Memory Leaks and Undefined Behaviour
We now have a few potential problems and these can even cause security flaws, crashes and other issues in applications or libraries we write. In fact not doing this kind of thing correctly has been estimated to be responsible for large parts of Microsoft vulnerabilities, so it's important to get this kind of thing right, see here and here for further information.
You need to make sure you:
- Free the memory when you're finished with it.
- Don't free memory twice.
- Don't dereference pointers that aren't initialised.
You might think this doesn't seem bad, and well, maybe this simple example doesn't seem so bad, but: (a) I refer you to the above articles of people making this mistake (recently there was a bug in Glibc, the core C library in many Linux systems that originated in 1991, see here), (b) Many developers used to more garbage collected language are not used to and prefer not to have to explicitly worry about freeing memory (c) Most C compilers won't warn you when you get this kind of thing wrong. See this program for example that's clearly violating the 2nd rule above.
#include <stdlib.h>
int main() {
int *i = malloc(sizeof(int));
*i = 1;
free(i);
free(i);
return 0;
}
I compiled and ran this on a Linux machine and got the following output:
strotter:c$ gcc -Wall -o c_double_free ./c_double_free.c
strotter:c$ ./c_double_free
free(): double free detected in tcache 2
Aborted (core dumped)
Point (a) is what's called a "memory leak" and points (b) and (c) both result in what's called undefined behaviour in C, the compiler's behaviour at this point is unpredictable. Crashing is one common option certainly, but not the only one.
This is about as much as you need to know about C memory management. Now let's move on to talk about how garbage collection made this a whole lot easier.
How Garbage Collected Languages Work
We've covered low level languages like C. Now let's discuss how garbage collected languages like Java, C#, JavaScript, Python, Ruby and many others work.
This is simpler in so many ways and a huge step forward. This is a large part of the reasons why Java became so popular in the 90s. You didn't have to worry about memory management and focus on the problems you were trying to solve. Garbage collection was a real game changer when it first came out and given the above problems with memory management in C it's not hard to see why.
In Java I can basically just say, give me an array of integers of unknown size, I'll add 5 integers to it, then delete 2 and carry on doing something else. Initially Java will automatically add 5 integers to the heap and initialise their values, we can't get this part of memory management wrong really. When we then remove 2 elements that we're not using any more, we don't need to worry about calling free on them as the JVM (Java Virtual Machine, it runs the Java program) calls it for us. The JVM will mark that area of memory as ready to free and it'll decide for us when that memory gets freed.
Can We Still Have Memory Issues in Garbage Collection?
So considering the problems we hit in the C world we see we're in a much improved world. Let's see if we can still hit some of the C memory problems we mentioned in the above section.
Not Freeing Memory
This is basically not possible any more within garbage collected languages and is one of their big selling points. You're not responsible for freeing memory at all, the garbage collector (sort of in the name really) just does this for you.
That's not to say creating memory leaks is impossible in garbage collected languages, you can certainly have memory leaks in Java if you're not careful, but it's a lot less likely you're going to have an issue than in C say. See this link for a great article on this.
Double Freeing Memory
The double freeing problem basically goes away in garbage collected languages assuming a correct garbage collector without bugs.
Dereferencing Non-initialised Pointers
This one is an interesting one, it kind of depends on the language a lot.
For example, in Java if I try the following program it fails saying not initialised:
strotter:java$ cat HelloWorld.java
public class HelloWorld {
public static void main(String args[]) {
String s;
System.out.println("s = " + s);
}
}
strotter:java$ javac HelloWorld.java
HelloWorld.java:5: error: variable s might not have been initialized
System.out.println("s = " + s);
^
1 error
This is still a big improvement though as this is caught at compile time. However I can cheat with this and bypass that compiler error as such:
strotter:java$ cat HelloWorld.java
public class HelloWorld {
public static void main(String args[]) {
String s = new String();
if (false) {
s = "Hello, World!";
}
System.out.println("s = " + s);
}
}
strotter:java$ javac HelloWorld.java
strotter:java$ java HelloWorld
s =
strotter:java$
Again though, this is doing something reasonably sensible (albeit it maybe slightly odd) and there's no undefined behaviour here.
In Python you can't really declare variables without setting their value so this issue goes away there.
Obviously if you reference an unknown variable you get a runtime error, which is just part of working with interpreted languages that don't have a compile step. For example, if I run the following Python program:
print(f"Just a one liner referring to an unknown variable {my_var}")
I get the following output:
strotter:python$ python unknown_variable.py
Traceback (most recent call last):
File "/home/strotter/work/blog/rust-article/python/unknown_variable.py", line 1, in <module>
print(f"Just a one liner referring to an unknown variable {my_var}")
NameError: name 'my_var' is not defined
In JS they basically default to the undefined value in JS. Again no undefined
behaviour issues.
In conclusion we see that a garbage collector basically solves a lot of these issues that we came across in C, however there are some penalties for this. Normally, except in the odd cases you absolutely can't, these penalties are normally worth it for the benefit they reap.
Disadvantages of Garbage Collector
The great news about a garbage collector is it makes our lives easier. The bad news is we lose some control. A lot of modern software developers find they can live with this and do so happily. However sometimes when the application is busy, they get paused by the JVM to force garbage collection, this can cause slowdowns and performance issues in the app (though there are things can be done when this happens).
Similarly if the garbage collection process kicks off at the wrong times, you may find you need more memory to run an application that might be necessary. This would have been a huge deal once upon a time, but RAM is really cheap these days, where developer salaries aren't. Sure maybe a non-garbage collected language might be slightly more efficient but the price of having to think about all of this constantly, garbage collection is generally well worth it and a great thing in the coding world.
Another problem with this approach is sometimes you're writing lower level code, an operating system is the obvious example, or something like embedded systems, you might not have enough on the system to run the garbage collector itself (not to mention something like the JVM). In this case you need a bit more control over the memory management and a lower level language like C is needed then.
How Rust does Memory Management
Now we move onto the Rust way of handling memory. In Rust, based on the code you write, the compiler statically analyzes your code and essentially adds in the free (drop in Rust) statements where they should be. This is a whole new way of doing management that is semi-unique to Rust. There are things in other languages like C++ has smart pointers that have some similarities. But Rust forces certain things that must be true that ensures that you get all the performance and advantages of C like languages, but without having to do all the memory management (and get it absolutely right) yourself.
In this section we'll begin by discussing ownership which is core to everything memory related in Rust, then we'll cover borrowing and the borrow checker that is super important to being productive in Rust. TODO...
Note that there is also "unsafe Rust" that is slightly different to the description given here. We only consider "safe Rust" in this article as that is what is recommended to use unless you really know what you're doing. Having to use unsafe is very rare and mostly available for the odd few cases like where performance is pivotal or you really can't do it any other way (most of these cases are covered off in the standard library however).
Ownership
Every bit of data in Rust is owned by a particular variable. This variable can pass ownership to another variable but it cannot share it, the owner of any data is always unique. Once the owner of that data is no longer in scope then Rust knows this data can be dropped (freed, but we will say dropped to match Rust terminology in this section).
So I don't want to get bogged down in Rust syntax for this article as it's aimed at people who don't know Rust, but as an example, consider the following (fairly simple) Rust program:
fn main() {
let s = "I am a string".to_string();
let name = "Steve".to_string();
let hello_world = get_hello_world(name);
println!("{hello_world}");
}
fn get_hello_world(name: String) -> String {
return format!("Hello, {}", name);
}
(For those that know Rust, I've deliberately made this as simple and readable as possible, hopefully even to those who haven't used Rust before. Yes technically I can do the second function without the explicit return, but that requires Rust knowledge I'm not assuming at this stage).
Before getting into the code itself, as an aside, you might wonder why the
exclamation mark in println!. Well that's really a subject for another time,
but it's because this is a Rust macro. Rust macro's are a way of allowing a
variable number of arguments that functions themselves don't support in Rust.
For us what we need to know is this prints a line. The {hello_world} inside
the string means put the value of the hello_world variable here.
Following the code now, we have three variables in the main function and one
in the get_hello_world function, and each of them are just a rust String for
simplicity reasons. They each have their own places that they get dropped. First
we have s that is created in the first statement of main. This one is really
straightforward and is available for the the whole of that function. I could
have put a println!("{s}"); as the last statement and it would have worked.
The next variable name might surprise you however. If I put a
println!("{name}"); at the end of the main function I'd get the following
error from Rust:
error[E0382]: borrow of moved value: `name`
--> test.rs:10:15
|
4 | let name = "Steve".to_string();
| ---- move occurs because `name` has type `String`, which does not implement the `Copy` trait
5 |
6 | let hello_world = get_hello_world(name);
| ---- value moved here
...
10 | println!("{name}");
| ^^^^^^ value borrowed here after move
|
note: consider changing this parameter type in function `get_hello_world` to borrow instead if owning the value isn't necessary
--> test.rs:13:26
|
13 | fn get_hello_world(name: String) -> String {
| --------------- ^^^^^^ this parameter takes ownership of the value
| |
| in this function
= note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider cloning the value if the performance cost is acceptable
|
6 | let hello_world = get_hello_world(name.clone());
| ++++++++
That's a whole lot to process and you don't need to know what all of it means.
But essentially when I pass name into the other function, I pass ownership of
name from main into the get_hello_world function. After this main can no
longer access this variable. Then this gets used in get_hello_world and then
it'll get dropped at the end of this function.
Lastly the hello_world variable is easy, it just drops at the end of the
main function.
So Rust figures out (fairly easily in this case) that this would be like having the following with explicit drops (NB: Never put drops in Rust like this unless you've a really good reason, Rust guys will think you don't understand Rust, and if you're doing this without good reason you probably don't):
fn main() {
let s = "I am a string".to_string();
let name = "Steve".to_string();
let hello_world = get_hello_world(name);
println!("{hello_world}");
drop(s);
drop(hello_world);
}
fn get_hello_world(name: String) -> String {
let ret = format!("Hello, {}", name);
drop(name);
return ret;
}
NB: Interesting fact, the drop function is just the empty function, see
here
if you don't believe me. The reason is it's just not needed, in fact all this is
doing is passing ownership of the value for name from get_hello_world into
the function drop, then this function immediately returns, Rust knows the
variable that owns this value has gone out of scope, and Rust adds in the drop
logic itself. The drop function itself doesn't actually drop anything any more
explicitly than if you didn't specify it at all (and you generally shouldn't).
Those with a keen eye might also wonder about the ownership of the return. We
are passing ownership of the string we created in get_hello_world back to the
main function with the owner being the variable hello_world.
This is a really trivial example, if it was all this easy C would have done this in the first place (well maybe). But it gets a lot more difficult when it comes to more complicated things like changing values dynamically, allowing other functions to read and write without taking ownership and that kind of thing. We'll cover some of this with borrowing next.
Borrowing
You might think looking at the above program "Well isn't that a bit inconvenient if I can't pass something into another function without changing ownership and losing it for the current function". Put simply, yes, that would be terrible, but that's not the only option available to us. We can also borrow in one of two ways, we can borrow with read-only access and we can borrow with read-write access.
This borrowing is done with references, we have two kinds:
- A shared reference - This is read-only and Rust knows when we hand these out nothing is going to change.
- A mutable reference - This gives read-write access and Rust knows the data is susceptible to change.
There are essentially two rules regarding references:
- If you have a shared reference you cannot change the data while that shared reference lives.
- If you have a mutable reference you cannot take any other references and only that mutable reference can change the data.
These two rules are enforced strictly by the Rust compiler by the infamous "Borrow Checker". Either I can have essentially unlimited readers and they all know the data isn't going to change or I can have a single thing that is writing and that knows that nothing else is going to write. This has far reaching consequences that we'll go into later.
Stack vs Heap in Rust
As a quick aside, you might have noticed that Rust memory management is very
similar to how C memory management happens on the stack. So you might wonder why
C couldn't just insert free statements. The answer comes because C doesn't
force you to have a unique owner like Rust does, that's the secret sauce here.
In C I could do:
int *i = malloc(sizeof(int));
*i = 1;
int *j = i;
int *k = i;
and this same bit of memory have three different pointers all pointing to the same data. C has no idea when you've stopped pointing to that data, but in the Rust world it knows every bit of data is uniquely owned, once that owner goes out of scope it's never going to be read or written to again, so Rust drops it and frees that memory.
Now you might be wondering things like does Rust uses the stack? Does it just use the heap for everything? Similar to some of the garbage collected languages, you don't necessarily have to know whether you're using stack or heap. Rust will basically default to the stack always as it's quicker, unless it can't and then it'll go for the heap. So if I create an integer it knows it can put that on the stack and it's more efficient than putting it on the heap, because an integer has a fixed size in memory this makes sense. On the other hand, strings and lists (called vectors in Rust) need the heap, so if you create these Rust will just use the heap. On the other hand again, a fixed size string goes on the stack.
Is there any Undefined Behaviour?
So Rust is very careful to avoid the possibility of doing this undefined behaviour. Let's have a look at how we Rust handles the 3 points above in the same way where we considered them for garbage collected languages.
Not Freeing Memory
This is actually possible in Rust, but really hard to do, you almost need to be doing it on purpose, and you certainly can do it on purpose. See here for an article on how to shoot yourself in the foot if interested, it seems unlikely you'll need to do this kind of thing much.
Generally speaking though, unless you do something like reference cycles, memory freeing takes care of itself in Rust.
Double Freeing Memory
As in garbage collected languages, the double freeing problem basically goes away as Rust won't put more than one drop in, and if you try to Rust will error. E.g. this program:
fn main() {
let s = "test".to_string();
drop(s);
drop(s);
}
results in a compiler error:
error[E0382]: use of moved value: `s`
--> double_free.rs:4:10
|
2 | let s = "test".to_string();
| - move occurs because `s` has type `String`, which does not implement the `Copy` trait
3 | drop(s);
| - value moved here
4 | drop(s);
| ^ value used here after move
|
help: consider cloning the value if the performance cost is acceptable
|
3 | drop(s.clone());
| ++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0382`.
So you're really going to struggle to get a double free past the compiler, the compiler will tell you you've done it wrong.
Dereferencing Non-initialised Pointers
Lastly let's try and dereference something that's not initialised in Rust. Let's try this program:
fn main() {
let s: String;
println!("{s}");
}
You'll get this compiler error:
error[E0381]: used binding `s` isn't initialized
--> print_uninit_var.rs:3:15
|
2 | let s: String;
| - binding declared here but left uninitialized
3 | println!("{s}");
| ^^^ `s` used here but it isn't initialized
|
= note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
help: consider assigning a value
|
2 | let s: String = Default::default();
| ++++++++++++++++++++
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0381`.
Now you might think you can cheat Rust into thinking it's initialised in the same way we tricked Java, let's try it:
fn main() {
let s: String;
if false {
s = "".to_string();
}
println!("{s}");
}
Will this trick the compiler, well we can run it and get this:
error[E0381]: used binding `s` is possibly-uninitialized
--> print_uninit_var.rs:6:15
|
2 | let s: String;
| - binding declared here but left uninitialized
3 | if false {
4 | s = "".to_string();
| -
| |
| binding initialized here in some conditions
| binding initialized here in some conditions
5 | }
6 | println!("{s}");
| ^^^ `s` used here but it is possibly-uninitialized
|
= note: this error originates in the macro `$crate::format_args_nl` which comes from the expansion of the macro `println` (in Nightly builds, run with -Z macro-backtrace for more info)
error: aborting due to 1 previous error
For more information about this error, try `rustc --explain E0381`.
So no, the compiler realised that there is a route where s is uninitialised,
and it won't allow that. You can however initialise it in every branch and
you're fine, for example, the following would compile OK:
fn main() {
let s: String;
if false {
s = "false".to_string();
} else {
s = "true".to_string();
}
println!("{s}");
}
Running this we get, as expected:
strotter:rust$ rustc print_init_var.rs
strotter:rust$ ./print_init_var
true
strotter:rust$
Note however this wouldn't work, Rust makes no attempt at seeing which branch something will follow, it just knows whether there is a possibility that a branch leaves something uninitialised:
fn main() {
let s: String;
if true {
s = "true".to_string();
}
println!("{s}");
}
This though is fine because it only gets used in that one branch that it is initialised.
fn main() {
let s: String;
if true {
s = "true".to_string();
println!("{s}");
}
}
The long and short is, no we can't have an uninitialised variable that we use, Rust will stop us.
In Conclusion
So hopefully at this stage we reasonably understand how Rust does memory management even if we don't necessarily know how. In future blog posts we'll revisit some of this, but this is fundamental to a decent understanding of Rust. If you've struggled previously to understand Rust memory management hopefully this has offered a small amount of insight for you.