LanguagesArchitecture

A few weeks ago, I was asked four questions all on the same day:

  • "When would we use C-like languages?"
  • "What language should I use for my game?"
  • "Why don't more people use Rust for web servers?"
  • "What are the benefits of borrow checking besides memory-safety and speed?"

The discussion had so many factors that I made it into a post, which very quickly exploded into a whole series. So here we are!

I love this topic because it's so nuanced: every language has its strengths and weaknesses, and there is no "one true language" that's best in every situation.

We'll mostly be comparing languages' approaches to memory safety, which is the prevention of common memory access bugs such as use-after-free.

Even if you're familiar with memory management, you'll likely learn some interesting things:

  • Less memory-safe languages are really well suited to a lot of situations!
  • Borrow checking has some pervasive hidden costs, and hidden architectural benefits!
  • Reference counting can be way faster than we thought.
  • Development velocity is often more important than run-time performance!
  • Accessing released memory isn't always a bad thing.

The Options

There are generally four approaches to memory safety:

  • Garbage collection (GC), like in Java, Go, Python, Javascript, etc. 0
  • Reference counting (RC), like in Swift, Nim, Lobster, etc.
  • Borrow checking, like in Rust, Cone, Cyclone, etc.
  • Manual memory management (MMM), like in C, Ada, Zig, Odin, etc.

There's also a fifth approach, generational references. We'll talk more about that elsewhere, this series is comparing the more traditional approaches.

Note that this is only Part 1. Subscribe to the RSS feed, twitter, or subreddit to watch for the rest!

The Tradeoffs

Memory safety approaches generally influence six aspects of a language:

  • Extent: How much memory safety does the approach offer?
  • Development Velocity: Are there obstacles to writing, changing, and maintaining code?
  • Speed: How fast does the code run?
  • Memory: How much memory does it consume?
  • Simplicity: Is your code simpler or more complex than with other approaches?
  • Correctness: Is the language more vulnerable to other kinds of bugs?

Different situations will prioritize these aspects differently, and will call for different languages.

Let's dive into the first one!

Extent

To what extent does each approach help with memory safety?

This is a surprisingly nuanced topic. It's not a black-and-white thing, approaches can be anywhere on the memory safety spectrum.

  1. Manual memory management (MMM) has no built-in memory safety protection.
  2. Tool-assisted MMM uses things like ASan, memory tagging, and CHERI to detect a lot of problems in development and testing.
  3. Architected MMM 1 uses more resilient patterns and architectures to drastically reduce the risk of memory unsafety even more.
  4. Statically-analyzed MMM uses frameworks like SPARK to be memory safe.
  5. Borrow checking is almost safe, but comes with the unsafe escape hatch which can cause UB, even in the safe code around it.
  6. GC and RC generally offer complete memory safety. 2

Let's talk about MMM first!

MMM Languages' Memory Safety

Manual memory management by default has no memory safety protections.

If a programmer allocates every object with malloc, 3 and gives it to free when it's last used, 4 the program will be memory safe... in theory.

In practice, it's quite difficult to make a memory-safe program that way.

On top of that, if someone later updates the program, they'll likely violate some implicit assumptions that the original programmer was relying on, and then memory problems ensue.

To make matters a bit worse, programs made this way will be quite slow:

  • malloc and free are expensive: they can increase a program's run time by as much as 25%.
  • Since these allocations are on the heap, we no longer get cache locality and cpu prefetching benefits. We'll talk about this more in the "Run-time Speed" section.

As you can imagine, many successful MMM projects avoid malloc for these reasons.

There is, of course, a much better and safer way to use MMM languages.

But before that, let's be a little more specific: what is memory safety, really?

Memory safety isn't what you might think

Memory safety prevents common memory access bugs, including:

  • Buffer overflows, where we attempt to access the nth element of an array, when n is actually past the end of the array.
  • Use-after-free, which is when we dereference a pointer after we free it.
  • Use-after-return, where we dereference a pointer to an object which lived in a function that has already returned.

These all have one thing in common: they risk accessing the wrong data, triggering undefined behavior ("UB") which can result in cantankerous shenanigans like security vulnerabilities, segmentation faults, or random nearby data changing. 5

But sometimes, accessing the wrong data won't trigger undefined behavior, if the data there is still the type that we expect. 6

So really, the goal of memory safety is to access data that is the type we expect.

This more accurate definition opens the door to a lot more useful, efficient, and safe approaches, as we'll see below.

And sometimes, it doesn't completely solve the problem

Note that sometimes, we can trade a memory safety bug for another kind of bug.

For example, if we free'd a ResponseHandler but never unregistered it, the NetworkManager might still have a pointer to it when the response comes, triggering a use-after-free.

The outcome might be different in another paradigm:

  • In GC, we'd still act on the response, resulting in mysterious behavior on the client. We might also cause a memory leak, despite having GC. 7
  • In a borrow checked approach, we might look up the handler by index from a central array, but something else has reused that slot, so we give the response to the wrong handler, resulting in odd behavior. 8

These are technically logic bugs, better than undefined behavior, but our work is not done. We still need good engineering discipline, testing, and proper data handling practices no matter what approach we use.

The safer way to use MMM languages

There are ways to drastically reduce the risk of memory safety problems, even when the language doesn't give you any protections itself.

There are some basic guidelines to follow:

  • Don't use malloc.
  • For long-lived allocations, use per-type arrays.
    • In a game, we might have an array for all Ships, an array for all Missiles, and an array for all Bases.
  • For temporary allocations, one can also use an arena allocator. 9
  • For temporary allocations whose pointers don't escape, one can also use the stack. 10
  • All unions must be tagged 11 and treated as values. 12
  • Always use bounds checking.

This is how a lot of embedded, safety-critical, and real-time software works, including many servers, databases, and games. 13

Interestingly, the borrow checker also nudges us in this direction, though we often use things like Vec, SlotMap, or HashMap instead of arrays to trade a little bit of speed for better memory usage. 14

This system mostly solves the aforementioned use-after-type-change bugs. To illustrate:

  • If we use a Ship after we've released it, we'll just dereference a different Ship, which isn't a memory safety problem.
  • If we use something in an arena allocator after we've released it, it will still be there because we never reuse an arena allocation for anything else.

These are still logic problems, but are no longer memory safety problems, and no longer risk undefined behavior.

Looking at modern MMM languages, this seems to be the direction they're emphasizing and heading toward:

  • Zig's standard patterns include allocator parameters, exemplified in its standard library.
  • Odin has a context system where you can use any allocator with any existing function, which means we don't need to specifically wire a function for it.

Both languages also have bounds checking by default, and all unions are tagged. 15

The benefit of this approach is that it gets us much closer to memory safety without the particular drawbacks of GC, RC, or borrow checking.

The safest way to use MMM languages

Practices like these have been formalized, and even integrated into static analysis tools like Ada's SPARK. One could even say the borrow checker is such a system, built into the language and enabled everywhere by default.

There are a lot of misconceptions about the safety of programs written in MMM languages.

  • Some believe that civilization will collapse if we keep using MMM languages. This belief is, of course, undermined by the vast swath of safety-critical software written in them that hasn't yet caused a mass extinction event.
  • Some believe that we can guarantee the safety of unsafe code and MMM code if we just think about it hard enough. This also isn't true.

But with the right tooling, practices, and discipline, one can reduce the risk of memory safety bugs to an acceptable level for their situation.

This is also why we use languages like Rust, even though unsafe blocks can undermine and cause problems in the surrounding safe code.

If one needs absolute safety, there are languages like Pony which have zero memory unsafety and less run-time errors than any other language, and tools like Coq.

But in the real world we often don't need absolute guarantees, and we can use something with sufficient memory safety, whether it uses constructs like unsafe blocks or tools like ASan or memory tagging or CHERI. 16

This is particularly nice because:

  • Without GC or RC, we can be as fast as possible.
  • We don't have to deal with the cognitive overhead or iteration slowdowns of SPARK and the borrow checker.
  • We can use fast approaches that the borrow checker and SPARK have trouble with, such as intrusive data structures and graphs, plus useful patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII 17 and higher RAII.
  • We can reuse code and libraries written in non-memory-safe languages.
  • We can use interesting features unique to unsafe and non-memory-safe languages.

So how do we know if we don't need absolute memory safety?

Side Notes
(interesting tangential thoughts)
0

By "garbage collection" I'm specifically referring to tracing garbage collection.

1

This isn't an actual term in the industry, but I think it captures the spirit nicely.

2

GC'd languages like Javascript and Lua are safe, and need no escape hatches.

3

This includes objects that would have been inline in the stack or in other objects.

4

This might not the place that C++'s unique_ptr frees the object, because that might accidentally not be the last use of the object.

5

Undefined behavior has also been known to cause computers to grow AIs and become sentient and hostile, probably.

6

Even this understanding isn't quite accurate. Memory unsafety theoretically can't occur if the memory is reused for a different struct type with the same layout, though in practice today's optimizers do interpret that as UB. If we want to go even further, we'd say that memory unsafety can only occur if we interpret a non-pointer as a pointer.

7

This is why Higher RAII is so nice, as it helps us remember to unregister handlers like this.

8

The proper solution to this is to use something like a SlotMap or HashMap that trades some performance for more intelligent reuse of space. In that case, we'd get an Option, and we can either panic, ignore it, or bubble it upward.

9

One must still make sure that a pointer to an arena-allocated object does not outlive the arena allocator.

10

A pointer "escapes" if it lives past the end of the object's stack frame.

11

A "tagged" union is a union that has an integer or an enum traveling alongside it, which keeps track of what the actual type is inside the union. One must always check the tag before accessing the data inside the union.

12

This means that we never take a pointer to a union, we instead copy it around. We might also only copy the data out of the union before accessing it.

13

For example, TigerBeetleDB has a similar set of rules.

14

Also check out Hard Mode Rust to see someone try to do this with completely pre-allocated data.

15

The creator of Zig is also looking into adding escape analysis, which is pretty exciting.

16

This also probably sounds odd coming from me, since Vale is completely memory safe. It would be very easy (and convenient) for me to claim that everyone should use my preferred level of memory safety.

However, a real software engineer puts their bias aside, and strives to know when an approach's benefits are worth the costs.

17

RAII is about automatically affecting the world outside our object. To affect the outside world, the borrow checker often requires us to take a &mut parameter or return a value, but we can't change drop's signature. To see this in action, try to make a handle that automatically removes something from a central collection. Under the hood we usually use unsafe mechanisms, including FFI.

When do we need memory safety?

Sometimes, we need memory safety to protect against very real risks:

  • When working with untrusted input, it can help protect us against security breaches.
  • When working with multiple users' data, it can help protect their privacy from errant use-after-free reads.
  • When working on safety critical devices, it can protect our users from harm.

But for other situations, like many games and apps, the costs and burdens of certain memory safety approaches might not be worth it.

Let's talk more about these risks and when they occur.

Memory Safety for Security-Sensitive Situations

Some programs handle untrusted input, such as web servers. An attacker can carefully craft input that takes advantage of UB to gain access to sensitive data or take control of the system. Memory safety helps guard against that.

For example, if working on a server or a multiplayer game, you're handling a lot of untrusted input and you'll want memory safety to help with that.

However, not all programs handle untrusted input. 18

For example, the Google Earth app is written in a non-memory-safe language but it only takes input from the user and from a trusted first-party server, which reduces the security risk. 19

In cases like these, security doesn't need to be as much of a factor in language choice.

18

"Untrusted input" can also be in the form of files. But if those files came with the program, such as assets for a game, then they are trusted input and not as much of a problem.

19

Its sandboxing also helps, whether from webassembly, iOS, or Android.

Memory Safety for Privacy-Sensitive Situations

Some programs reuse memory for multiple users. A use-after-free could mean that your web server could expose a user's private data to another user.

For example, let's say a server receives Bob's SSN from the database, but needs to wait for a second request before sending it all to Bob's phone.

While Bob's SSN is hanging out in RAM, some buggy code handling Jim's request might do a use-after-free and read Bob's SSN, exposing it to Jim.

Memory safety helps by preventing use-after-frees like that.

Note that memory safety does not necessarily solve the problem. Borrow checking can turn memory safety problems into privacy problems, and the same can be true of MMM approaches. 20 No approach is perfect, but GC and RC seem to be the most resilient here.

However, not all programs handle data for multiple users.

For example, Shattered Pixel Dungeon 21 is a mobile roguelike RPG game that just stores high scores and save files for a single user.

In cases like these, privacy doesn't need to be as much of a factor in language choice.

20

Generational indices, memory tagging, and CHERI can help with this drawback.

21

This game is amazing, it's open source, and I'm a proud sponsor!

Memory Safety for Safety-Critical Situations

Some programs have safety critical code, where a bug can physically harm a user. The Therac-25 had a bug that dosed six patients with too much radiation. One should definitely use a memory safe language for these cases.

However, most programmers aren't writing safety-critial code. My entire career has been on servers, apps, and games, and I generally don't connect them to anything explosive, incendiary, or toxic to humans.

Sometimes the worst case isn't that bad

Sometimes, memory unsafety bugs aren't as bad as all that.

For example:

  • In Google Earth, the occasional memory safety bug might crash the page and force a refresh, thus caused a 1-2 second inconvenience for the user.
  • In modern multiplayer games (plus older ones like Warcraft 3), when the program crashes, the players can restart and resume where they left off.
  • In a music player app, the user just restarts the app.

Bugs like these are generally as severe as logic problems, and we can use less burdensome techniques to detect and resolve them: tooling like ASan, Valgrind, release-safe mode, memory tagging, CHERI, etc. They aren't perfect, but they're very effective. We'll talk about these more below.

So what are these tools, and how might they help us easily improve our memory safety?

Memory-safety tooling for MMM languages

Sanitizers

The easiest way to detect most memory safety bugs is to use tools like ASan, memory tagging, valgrind, etc. These are usually turned off in production, but we turn them on in:

  • Development.
  • Testing, especially integration tests.
  • Canary servers.

The Google Earth folks used these pretty religiously. It might be surprising to hear, but the vast majority of memory safety bugs were caught in development and automated tests by Address Sanitizer. 22

In an average Google Earth quarter, they would get perhaps 60-80 bug reports, and memory unsafety was the root cause of only 3-5% of them. That's how effective Address Sanitizer can be.

CHERI

On more modern hardware, you can also compile MMM languages with CHERI.

CHERI works by bundling a 64-bit "capability" with every pointer, thus making every pointer effectively 128 bits. When we try to dereference the pointer, the CPU will check that the capability is correct, to help with memory safety.

It has surprisingly little run-time overhead!

Sandboxing with wasm2c

If you want to call into a library written in an MMM language, then you might benefit from using wasm2c, for a modest performance cost (14% with all the platform-specific mechanisms enabled).

Note that there can still be memory corruption inside the sandbox, which may or may not be an acceptable risk for the situation.

Memory Tagging

Memory tagging is a technique that takes advantage of how pointers and addresses work on modern operating systems.

A pointer is 64 bits, which means we theoretically have 2^64 bytes of address space. In reality, operating systems only use 48 to 56 bits of that, and don't use the other bits for addressing.

Memory tagging will generate a random 4-bit number for every chunk of memory. Whenever we create a pointer to that memory, it will put that 4-bit number into the top unused bits of the pointer. Later, when we try to dereference the pointer, it will check that those 4 bits still match the original 4 bits of the object. If they're different, that means the object has been freed already, and it will halt the program.

This is particularly good for debugging and testing. If this is enabled for your integration tests, then any invalid access bug has a 94% chance of being caught. 23

MMM and Memory Safety

That pretty much covers the various approaches one can use with MMM, and to what extent they help with memory safety.

A bloody tome

...said my friend when he saw how long this post was! It was already 45 pages and growing, so he had me cut it off here at 11. 24

In the next posts, we talk about:

  • The extent of memory safety offered by borrow checking, GC, and RC.
  • Development velocity.
  • Run-time speed.
  • Memory usage.
  • Correctness.
  • Simplicity.

And at the very end, we'll have a comprehensive answer for when to use which approaches.

Thanks for reading! I hope this post has been intriguing and enlightening.

In the coming weeks I'll be continuing this series, so subscribe to the RSS feed, twitter, or the subreddit, and come hang out in the discord server!

If you found this interesting or entertaining, please consider sponsoring me:

With your help, I can write this kind of nonsense more often!

22

They didn't even use shared_ptr, they mostly used unique_ptr and raw pointers.

23

And that chance increases to 99.6% if you run your integration tests twice, and so on!

24

And I haven't even covered the more interesting tools like ReleaseSafe mode, UBSan, or the various temporal memory safety approaches! But we've covered the basics.