Memory leaks are memory safe, and there isn't much to do about it

I really like the Rust programming language, it's basically my top pick for any project where I have control over what language to use, barring really small scripts where I typically go for Python instead. Rust's strict compiler provides some really nice safety guarantees, which allows me to not make silly mistakes and still get really nice performance.

But sometimes when Rust's safety guarantees come up, somebody will point out that memory leaks are considered safe in Rust. I think sometimes it's said as a word of warning that you can't fully let your guard down but I guess sometimes it's also said as a kind of a dismissal of Rust's safety guarantees in general.

It came up again in a chat recently and a thought popped into my head that memory leaks probably can't be fully addressed and prevented because of a rather fundamental problem in computer science. Finally, I get to put that newly acquired computer science degree to work!

What is a memory leak?

Memory leaks are when a program inadvertently allocates an increasing amount of memory without releasing it. Memory leaks can be big or small, but usually the bigger the leak the more we care about it. The main thing is that as the longer the program runs, the more memory it ends up allocating until eventually the system might run out of memory, which typically causes the program to crash, possibly along with many other programs.

This means that memory leaks can be rather destructive as far as bugs go. They can be tricky to locate, since they don't necessarily produce an easily accessible stack trace, and nothing is quite as annoying as your entire system grinding to a halt as the RAM gets filled and the system starts thrashing with slow swap memory until eventually the out-of-memory killer finds the offending process and kills it, and even then it might take a while for the system to empty the swap memory and get back up to speed. I have intentionally disabled swap partitions and swap files on my system and I've used EarlyOOM to kill processes before the system is completely out of memory.

Despite their potential for destruction, Rust considers memory leaks "memory safe" and thus doesn't aim to prevent them. Rust's design, however, makes it less easy to create memory leaks, since it uses a Resource Acquisition Is Initialization (RAII) pattern to abstract resource allocation and deallocation. Contrast to C, where memory is allocated usually through malloc() and you must always follow that up with a call to free() to ensure the memory is freed. Forgetting to free() your memory always creates a memory leak and calling free() twice on the same memory is Undefined Behaviour. But it's still possible to create memory leaks in Rust by, for example, endlessly adding values to a list or by creating reference counting pointers that point at each other, which causes the reference cycle to never be freed.

The Halting Problem, or why we can't have nice things

So, why can't we just have the Rust compiler flag memory leaks, like it prevents us from creating data races or accidentally pointing to a variable that was already freed?

Well, this is where the rather fundamental Halting Problem comes into play. The Halting Problem originates from the time before computer science was really even a thing and it has some interesting implications in computer science. The problem can be expressed as follows: can a program be devised such that when given any program as input, it will be able to determine if that program will halt or not. Unlike various other problems, like the P = NP problem, the Halting Problem is nice in the sense that Alan Turing proved without a shadow of a doubt that it's undecideable, meaning that it's impossible to create such a program that can determine if any program halts of not.

There's a couple of proofs for this, but the easiest is a proof by contradiction. Suppose we have a program P that takes another program as input. If the input halts, then P doesn't halt and if the input doesn't halt P halts. Basically, P always does the exact opposite of its input. Now, what happens if we feed P to itself as input? If P were to halt, then P should not halt but that would contradict itself. Essentially what you end up with is a paradox, and thus we can determine that a program such as P cannot be created.

Because we now know that the Halting Problem is undecideable, we can use it as a tool to determine the computability of other problems. Basically, if the solution to any problem would make it possible to solve the Halting Problem, we know for a fact that the solution is not possible.

So, how does this relate to memory leaks again? We can use the Halting Problem to determine if detecting and thus eliminating memory leaks would make it possible for us to solve the Halting Problem. Because, as it turns out, memory leaks can be substituted for halting with the same logical consequences.

The two main ways of safely leaking memory in Rust are to either create a reference cycle or to continuously add elements to a growing data structure without ever freeing them. So, for the Rust compiler to eliminate safe memory leaks, it would need to be possible for at least these classes of memory leaks to be detectable.

Detecting reference cycles

The Rust Book provides the following example of reference cycles:

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));
    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

    if let Some(link) = a.tail() {
        // a now refers back to b
        ,*link.borrow_mut() = Rc::clone(&b);
    }
}

In this case the Rust compiler would need to realize that b already points to a and that at the end of the code a is changed to refer back to b. With this code it's pretty obvious to figure out and a bit of code could be written to detect this particular example of reference cycles.

However, let's make the code a bit more complicated:

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));
    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

    arbitrarily_complex_function_that_may_or_may_not_halt(&a, &b);

    if let Some(link) = a.tail() {
        // a now refers back to b
        ,*link.borrow_mut() = Rc::clone(&b);
    }
}

The function call in the middle can be substituted with any code that can be represented in Rust. And since Rust is a Turing complete language, this can be any possible computation. Can we now confidently detect the reference cycle and thus the memory leak?

I would argue not, since now the Rust compiler would need to be able to resolve what may or may not happened to a and b in the arbitrary code and it would need to determine if that function will actually return or not. If this were possible, we would be able to solve the Halting Problem, which proves that it's not possible to detect the reference cycle before executing the program.

Detecting leaks in growable collections

The second type of memory leak is a slightly simpler one, which isn't even mentioned in the book because it's so obvious. To leak memory, we need to simply add elements to a growable collection, such as a Vec, a LinkedList, a VecDeque or any other such growable collection. An example of this could be:

fn main() {
    let mut vector: Vec<i32> = Vec::new();

    loop {
        vector.push(0);
    }
}

This example would be relatively easy to detect. Rust already has dead-code detection and can detect obvious infinite loops, such as this one. The problems arise when these collection manipulations happen in more complex code.

But since these leaks in growable collections imply that the memory is leaked because the program never stops appending to the collection, this is the very definition of a Halting Problem: we are trying to figure out if the adding of new elements to the collection ever halts or not. Thus we can safely say that it's not possible to confidently detect all memory leaks due to growable collections.

Some asterisks apply

It's worth pointing out, however, that the Halting Problem only means that it's not possible to write a program that will figure out if any program will halt or not. It is possible to write programs that can detect if some programs will halt or not. For example, detecting simple infinite loops is already something the Rust compiler can do to detect dead code. Figuring out halting only becomes difficult when dealing with arbitrarily complex programs.

The same logic applies to these memory leaks. It may be possible to detect certain examples of reference cycles or infinitely growing collections. Or the compiler could detect instances of code that appear like they could cause memory leaks, but the problem there is about how conservative or lenient you want to make the detection system.

The main point of this whole thing is that it doesn't seem possible to confidently detect and thus eliminate all memory leaks. So, if you cannot solve a class of problems it probably makes sense to only attempt unintrusive mitigations but otherwise classify it as acceptable "safe" behaviour in the sense that the detection systems cannot prove your code to not exhibit that behaviour.

And all things considered, memory leaks are memory safe in the sense that small memory leaks don't usually affect the execution of the program. Particularly with reference cycles, the amount of leaked memory is most likely quite small and practically unnoticeable. Most of the destructive forms of memory leaks are usually rapid and relatively obvious.

Rust could theoretically enforce stronger safety guarantees by making successful allocations explicit. This means that every time you create a new variable you'd get back a result that you would need to check for success or failure. This way it would always be on the programmer to figure out if the error is fatal or not. But this would only be a reactive measure to a low-memory situation rather than a preventative measure to memory leaks. Enforcing this behaviour in every allocation, be it stack or heap, would also make Rust quite clunky to use, and it's likely a programmer would just have the program crash on an allocation failure anyway rather than try to figure out how to free enough memory to get back into an operational state. Reactive measures to low-memory can already be implemented in Rust explicitly in situations that require such functionality.

Anyway, that's been that. I don't think this post has necessarily brought up anything too new and exciting, but I felt like writing a bit about the relationship between the Halting Problem and memory leaks. Hopefully somebody found this interesting.